Question:
There is long list of natural numbers. Remove every 2nd no from list in 1st pass. Remove every 3rd no from list in 2nd pass. Find whether Nth natural no will exist after P passes. N and P are inputs.

Example: N is 15 and p is 3.
Initial: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
After 1st pass: 1 3 5 7 9 11 13 15 17 19
After 2nd pass: 1 3 7 9 13 15 19
After 3rd pass: 1 3 7 13 15 19
After 4th pass: 1 3 7 13 19

So we see that 15 exists after 3 passes but vanishes after 4th pass.

Another version of the same question is:
Check if Nth natural number will stay in the string or vanishes. Also after how many passes, you can say that it will stay/vanish.

Answer:
One way to check is to reconstruct entire string after every pass and check for number. That is too complex and takes lot of time. Another way is to just calculate the position of N after every pass and save this new position as current for next iteration.

How do we calculate the new position after Pth pass. We see that in any of the pass new position will be decreased by no of elements deleted between 1 and current position.

(NEW POS) = (CURRENT POS) – (NO OF ELEMENTS DELETED BETWEEN 1 AND CURRENT POS)


Also we see that in ith pass we are deleting every (i+1)th elements, so we can say Pos(i-1)/(i+1) element will be deleted between 1 and N. Where Pos(i) is position of N after (i) passes. Also we are seeing that an element will be vanished if N/(i+1) is an integer.

P(i) = P(i-1) - P(i-1)/(i+1)

After how many passes, you can say that it will stay/vanish: We can easily stop, when either P(i-1)/(i+1) is an integer – Vanishes

Or

P(i) < (i+1) – Stays forever

Code:
bool check_posiiton(int n, int p)
{
int cur = n;
int i = 0;
while (i <= p)
{
i++;
if (cur%(i+1) == 0)
{
//Vanishes in this pass
return false;
}
else if (cur < (i+1))
{
//Number exist denominator is greater than numerator
return true;
}
cur = cur - cur/(i+1);
}
return true;
}

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.