Monday, March 24, 2014

Check if any number exists in the list after removing them from particular positions in natural number progression

Problem
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.

Solution
Method 1 - brute force
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.

Method 2 - 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)


So, if p = 1, then number of elements deleted will be N/2, and position of N will become N - N/2. So, in example position of 15 becomes 7.
if p = 2, then number of elements deleted will be CurrentPosition/3 as we will be deleting every 3rd element. Now, position of N will become CurrentPosition - CurrentPosition/3.

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

Here is the code to handle this
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;  
}  

Thanks

Reference - http://tech-queries.blogspot.in/2011/02/check-if-number-exist.html ,

0 comments:

Post a Comment