CareerCup

This is similar to the Door Toggling Puzzle.
http://classic-puzzles.blogspot.com/2008/05/door-toggling-puzzle-or-100-doors.html

why are 5,11,.. removed?

becuase when jump=3, every third element will be removed from the remaining elements after jump=2.

@Anonymous on September 12
I don't think this problem is related to the 100 doors puzzle, though you may feel it similar in the first look. here is why:
#. In the door puzzle the numbers of doors are static i.e after each operation[closing, opening] the door number does not change. In case of our puzzle, the Q attaches the position as the face number for that element. Let revisit the example,
consider 1,2,3,4,5,6,..... infinite ...
jump=2.
then 2,4,6,8 .... gets removed. here every second element from the list gets removed and we've the
remaining list as: 1, 3, 5, 7, 9, 11, ...
Now for jump=3, every third element from the above list[we're talking about the current position of the elements] gets removed and we've the following list,
1, 3, 7, 9 ....
I guess the question is now pretty much clear.

So what is the solution to test if a number is blessed or not?

I believe following would be the solution for testing if the number is "blessed" or not.

The basic premise is that with each turn the number of elements in the sample set (numbers below n) are decreasing. The trick is to find out if n gets eliminated or not.

Lets say the number is 99.

1. In first cut 99 div 2 = 49 (will get removed), so 99 - 49 = 50 elements are left, note here the mod is not zero
2. In second cut 50 div 3 = 16, so 50 - 16 = 24 elements are left, and the mod is again not zero
3. In third cut 24 div 4 = 6, and the mod is zero i.e. the number will get eliminated
so it is "not blessed"

Lets say the number is 7
1. 7 div 2 = 3, mod = 1, 7 - 3 = 4
2. 4 div 3 = 1, mod = 1, 4 - 1 = 3
3. 3 div 4 !!!!! (number is blessed, as there are less elements left in my sample set than the cut)

Lets say the number is 31
1. 31 div 2 = 15, mod = 1, 31 - 15 = 16
2. 16 div 3 = 5, mod = 1, 16 - 5 = 11
3. 11 div 4 = 2, mod = 3, 11 - 2 = 9
4. 9 div 5 = 1, mod = 4, 9 - 1 = 8
5. 8 div 6 = 1, mod = 2, 8 - 1 = 7
6. 7 div 7 = 1, mod = 0 !! (Number will get removed)

public static boolean numberBlessed(int n) {
        int i = 2;
        int mod = 0;
        int div = 0;
        while (n >= i) {
            div = (n / i);
            mod = (n % i);
            if (mod == 0) {
                return false;
            }
            n = n - (div);
            i++;
        }
        return true;
    }

Thoughts ???

yup,
thats the perfect solution.

but, any other solution using any data structure.

Here are my thoughts...not sure though. Please feel free to comment &/or rectify :::

Original Sequence :: 1,2,3,4,5,6,7,8,9,10..
After jump2, Altered Sequence:: 1,3,5,7,9..
After jump3, Altered Sequence:: 1,3,7,9,..

Notice that the set of all numbers in the sequence before the first cut element are blessed and also is the case of the element immediately after the first cut element, as it takes the place of the first cut element after alteration & the same time the jump has incremented by 1 for the next iteration. So all these elements are certainly 'blessed'.

Eg -- For jump2 , first cut element in the original sequence is a[(jump-1)]=a[1]=2
Therefore {1} as it is before the first cut element and {3} as it is the next element to the first cut element, are blessed.

After jump 2, Altered Sequence:: 1,3,5,7,9..
Now for jump3, first cut element shall be a[(jump-1)]=a[2]=5
Therefore {1,3} are blessed as they are before the first cut element 5 [we understood that in the first pass itself] and also 7 as it is the next the first cut element.

And so on....On the other note, we may ascertain `blessedness` of a particular element
when it is less than, or `just` greater than the first cut element. So for larger n,
the proposed algorithm may have performance issues

And then ...just forgot to mention....THOUGHTS on the above approach??

SNL's solution is perfect and amit's approach seems to be working, though. BTW, which of these two is more efficient? SNL, would you like putting couple of lines of explanation behind your logic[why mod, why subtracting the mod to get the remaining value etc]. That would be nice for us to follow. blindly accepting a solution doesn't make sense as the interviewer expects you to come up with a solution and the logic of doing that. Thank you.

SNL's algorithm works just fine...my approach,even though looks ok, may not be efficient as it is involves multiple iterations of the sequence & would largely be dependent on the number which is be checked if its blessed or not & the size of the sequence {if its infinite sequence, as the problem suggest...we had it,:). In fact I tried coding it up, I assumed a finite sequence.}
In short, SNL's implementation wins.

@SNL : Your approach seems to be correct. But 99 would be removed at step 6 ie. when jump is 7
(mistake above 50-16 = 34 and not 24)

Another approach to this problem is ...

when jump is j ,
A number n would be removed at that jump if
(n-1)/j + (j-1) is divisible by j.

Comments ???

@Anonymous on October 02, 2009:
care to elaborate or give a proof ?

a slightly diff. approach based on the position of the number after every iteration.
position begins with 1.

int get_log(int num, int base) {
    int times = 0;
    while (base <= num) {
        times++;
        num -= base;
    }
    return times;
}

bool is_blessed(int n) {
    int k = 2;

    while (k <= n) {
        if (n % k == 0) {
            return false;
        }
        n -= get_log(n, k);
        k++;
    }
    return true;
}

cheers :)