bool isLucky(int n)

Before every iteration, if we calculate position of the given number, then in a given iteration, we can determine if the number will be deleted. Suppose calculated position for the given number is P before some iteration, and each Ith number is going to be removed in this iteration, if P < I then input number is lucky,

if P is such that P%I == 0 (I is a divisor of P), then input no is not lucky.

How to calculate Next position of the number:

We know that initially the position of the number is nth itself. Now any next position will be equal to the previous position minus the number of elements (or say items) removed.

That is, next_position = current_position – count of numbers removed

For example, take the case of n=13.

We have: Initial position: n, ie. 13 itself.

1,2,3,4,5,6,7,8,9,10,11,12,13

Now after removing every second elements , we actually removed n/2 elements. So now the position of 13 will be : n-n/2=13-6=7 (n=13), i=2

1,3,5,7,9,11,13.

After that, we remove n/3 items. Note that n now is n=7. So position of 13 : n-n/3 = 7-7/3 = 7-2 = 5 (n=7), i=3

1,3,7,9,13

So next it will be : n-n/4 = 5-5/4 = 4 (n=5), i=4

1,3,7,13

So now i=5, but since position of 13 is 4 only, so it will be saved. Hence a lucky number! n=4, i=5

// C++ program for Lucky Numbers

#include <bits/stdc++.h>

using namespace std;

#define bool int

/* Returns 1 if n is a lucky no.

otherwise returns 0*/

bool isLucky(int n)

{

static int counter = 2;

if(counter > n)

return 1;

if(n % counter == 0)

return 0;

/*calculate next position of input no.

Variable "next_position" is just for

readability of the program we can

remove it and update in "n" only */

int next_position = n - (n/counter);

counter++;

return isLucky(next_position);

}

// Driver Code

int main()

{

int x = 5;

if( isLucky(x) )

cout << x << " is a lucky no.";

else

cout << x << " is not a lucky no.";

}