Microsoft Interview Question Software Engineer / Developers
If we remove the elements from the fixed list(removed positions are not filled by next index) then if suffices to check if
for 1<i<=p , i is a factor of N. If so it will not exist. Thus prime numbers will never be removed if they are > p.
Ques:whether n th number exist after p passes?(not a circle list)
Ans:
Simply, we only need p times check, one check for each pass.
int i=1;
//t means that every t th number is removed for current pass
int t=2;
for(;i<=p; ++i, ++t)
{
if(n%t==0)
return true;
n=n-n/t;
if(n<0)
return false;
}
/**********explanation*************
*make the input position n as our judging position
*after each pass, we update its new postion by n=n-n/t;
*because each pass, we remove n/t values before it
*if n%t equals to 0, it will be removed at current pass
*after updating n , that if n is below 0
*then it can exist for ever, since later pass will not remove it
***********************************/
thanks for the idea. it doesnt work for n=7, p=4. Here is a modified version
bool doesExist(int n, int p)
{
//Simply, we only need p times check, one check for each pass.
//t means that every t th number is removed for current pass
for(int i=1, t=2;i<=p; ++i, ++t)
{
if(n%t==0)
return false;
n=n-n/t;
if(n<0)
return true;
}
return true;
}
As per my understanding, 3rd no. from list means from the remaining list. Also we cant consider it as circular list. Let me know my understanding is correct or not.
- DD March 23, 2010