Problem
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.
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
Thanks
Reference - http://tech-queries.blogspot.in/2011/02/check-if-number-exist.html ,
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