What number remains after repeatedly eliminating perfect squares?

Question

I was practicing SRM Problems in Topcoder.I came across this problem

Problem Statement: Today is the Christmas Eve. People around the world celebrate this holiday. The following story takes place in the land of reindeer, where Santa Claus resides.

The reindeer love candies. They have n pieces of candy. The pieces of candy are numbered 1 through n. Dasher is one of the reindeer. He wants to eat one of the candies. To pick the one he will eat, Dasher uses the following method: While there is more than one piece of candy: Discard all candies that are numbered by perfect squares (i.e., candies 1, 4, 9, 16, 25, etc.). Relabel the remaining k candies 1 through k, keeping the numbers in the same order. Once only one piece of candy remains, Dasher will eat it.

You are given an int n. Your method must compute and return the number initially assigned to the piece of candy eaten by Dasher.

I solved the problem using ArrayList but my solution fails for very large numbers(Java Heap Sapce Exception ).Thus i was thinking whether it is possible to solve the problem in O(1) space complexity.

Please give your suggestions and approach. I do not want the code please explain only the logic to crack this problem.

I have reopened this Question with problem statement so that maestroes in Stackoverflow can help me to crack this problem in O(1) Space complexity

Answer 1

Another variant of the same:

a = floor(sqrt(N-1))
b = min((N-1)/a, a+1)
solution = a*b+1

Or, stated differently,

unsigned long long eats(unsigned long long N) {
    unsigned long long r = (unsigned long long)sqrt(N-1);
    while(r*r >= N) --r;
    while(r*(r+2) < N) ++r;
    if (N <= r*(r+1)) {
        return r*r+1;
    }
    return r*(r+1)+1;
}

The proof follows from analysing the next function which gives the next position of any candy, next(n*n) = 0, so that it's not a partial function. If a*a < N < (a+1)*(a+1), we have next(N) = N - a. So a number of the form n = a*(a+1) + 1 travels

a*(a+1)+1 -> a*a + 1 -> (a-1)*a + 1 -> ... -> 2*3 + 1 ->2*2 + 1 -> 1*2 + 1 -> 1*1 + 1 -> 0*1 + 1

We see that also numbers of the form a*a +1 reach 1. Numbers of any other form reach a square larger than 1 at some point:

a*(a+1) -> a*a -> eliminated
a*(a+1) + r -> a*a + r -> (a-1)*a + r

for 2 <= r <= a. If r = a, (a-1)*a + r = a*a is a square, resulting in immediate elimination. If r < a, the number reached after two steps has the same form with the same r. Continuing, it follows that the number reaches

(r+1)*(r+2) + r -> (r+1)*(r+1) + r -> r*(r+1) + r -> r*r + r -> r*r -> elimination.

So we have seen

• A number reaches the spot 1 in the process if and only if it is of the form n*n + 1 or n*(n+1) + 1

The last number to reach the first spot starting with N candies is of course the largest number of that form not exceeding N. QED.

Answer 2

I believe that the following solution works correctly and uses O(1) memory, assuming you can hold an integer in O(1) space. The idea is to try to run this process backwards until you end up finding the ultimate position of the correct piece of candy.

Let's trace through an example of this problem where n = 10. We then get this:

1  2  3  4  5  6  7  8  9  10
X        X              X

2  3  5  6  7  8  10
X        X

3  5  7  8  10
X        X

5  7  10
X

7  10
X

10

Now, suppose that we want to compute the final result for this problem. We know that when we're done, the candy eaten is at position 1, since there's only one piece of candy left. So let's try setting it up like this:

1

Now, we know that on the previous iteration, the candy at index 1 must have been eaten. This means that the final candy was actually at position 2 last time:

?   2

On the iteration before this, we know that since candy 1 was eaten, our candy must actually have been at position 3:

?   ?   3

At this point, we again think back one iteration. We know that candy 1 was eaten, but candy 4 was eaten as well. This means that the index of our candy must have been 5 on the previous iteration, since when we scoot it down to its proper position it must have skipped back one spot for the 1st element and one spot for the 4th element:

?   ?   ?   ?   5

Repeating this same logic, we get that the previous index would have been 7:

?   ?   ?   ?   ?   ?   7

Now, for the next step, we know that we would have scooted the candy down two positions because we dropped out the 1st and 4th elements. However, this would put our candy at position 9, which would have been deleted. This means that instead we'd bump the candy to position 10:

?   ?   ?   ?   ?   ?   ?   ?   ?   10

At this point, since there are 10 candies left, we know that we've fully reversed the process and are done. Since the final resting spot of our candy was position 10, we know that the answer is that the 10th candy is the one that was eaten, which perfectly matches our previous work!

The trick behind this approach is that we don't need much memory to make it work. In particular, at each step we need to keep track of only a few things:

• What index is the final piece of candy currently at? We need this to know where to stop.
• How many squares are below that index? We need this to know how many elements are getting deleted on each step.
• What is the next perfect square? We need this to know when the number of squares getting deleted each time increases.
• What was the last index we explored? This algorithm works by running the process backwards, so at some point we're going to realize that we've run it one time too many. When this happens, we need to be able to "back up" a step to get to the last index that didn't overshoot.

Given this, we have the following algorithm:

• Set the current index to 1.
• Set the number of smaller perfect squares to 1.
• Set the next perfect square to 4.
• Set the last smaller index to be 1.
• While the current index is less than n:
  • Set the last smaller index to be the current index (remember the solution so far).
  • Set the current index += the number of smaller perfect squares (run the process backwards one step)
  • If the current index is equal to the next perfect square, add one to it (an edge case of running it backwards; if we hit a perfect square, we should be one step past it)
  • If the current index is greater than the next perfect square (there are now more numbers being deleted each step):
    • Set the perfect square to be next the perfect square.
    • Add one to the number of perfect squares smaller than the index.
• Return the last smaller index.

This requires only O(1) memory to hold all of the values.

Let's try an example! With n = 20, if we work through the formal process, we get this:

1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
X        X              X                    X 

2  3  5  6  7  8 10 11 12 13 14 15 17 18 19 20
X        X              X                    X 

3  5  7  8  10 11 13 14 15 17 18 19
X        X              X

5  7 10 11 13 14 17 18 19
X        X              X

7 10 13 14 17 18
X        X

10 13 17 18
X        X

13 17
X

17

If we run our algorithm, we get

 Current Index       Next Square      Smaller Squares
 1                   4                1
 2                   4                1
 3                   4                1
 5                   9                2
 7                   9                2
 10                  16               3
 13                  16               3
 17                  25               4
 21                  25               4

Since 21 > 20, the last smaller index is 17, so we return 17, which is the correct answer!

Written as C code, assuming no integer overflow:

int EatenCandyIndex(int n) {
    int currIndex = 1;
    int numSmallerSquares = 1;

    /* Rather than tracking the next square, track the root of the next
     * square.  We can just square this to get the next square.
     */
    int rootOfNextSquare = 2;

    /* The last spot where the candy would be before we had Too Much Candy. */
    int lastIndex = 1;

    while (currIndex <= n) {
        lastIndex = currIndex;

        currIndex += numSmallerSquares;
        if (currIndex == rootOfNextSquare * rootOfNextSquare)
            ++currIndex;

        if (currIndex > rootOfNextSquare * rootOfNextSquare) {
            ++numSmallerSquares;
            ++rootOfNextSquare;
        }
    }

    return lastIndex;
}

However, as written, this algorithm is not particularly efficient. Specifically, look at its behavior in the example where n = 20. Note that we have three rounds where the step size is one, two with the step size two and three, etc. Rather than having those rounds occur explicitly, we could instead compute how many rounds are going to have to occur with that step size, then just run all of those steps at once. This way, we always have one round with size one, one round with size two, one round with size three, etc. To do this, at each step we will need to see what our next target is; this will either be the number n or the next perfect square. Once we've found our target, we need to see how many steps are required to get there. If the current index is i and our target is t, and if our step size is k, then we need to take ⌈(t - i) / k⌉ steps to get there. Using a cute trick with integer division, we can compute this as

int numSteps = ((t - i) + (k - 1)) / k;

This gives us the following updated algorithm:

int EatenCandyIndexFaster(int n) {
    int currIndex = 1;
    int numSmallerSquares = 1;

    /* Rather than tracking the next square, track the root of the next
     * square.  We can just square this to get the next square.
     */
    int rootOfNextSquare = 2;

    while (true) {
        /* Figure out what our target is. */
        int target = min(n, rootOfNextSquare * rootOfNextSquare);

        /* See how many steps are required. */
        int numSteps = ((target - currIndex) + (numSmallerSquares - 1)) / numSmallerSquares;

        /* See where we'd end up if we took one fewer than this many steps forward. */
        int lastIndex = currIndex + (numSteps - 1) * numSmallerSquares;

        /* Take that many steps forward. */
        currIndex += numSmallerSquares * numSteps;

        /* There is an edge case here: if we hit our number but it's a perfect square,
         * we want to return the previous value.
         */
        if (currIndex == n && n == rootOfNextSquare * rootOfNextSquare)
            return lastIndex;

        /* Otherwise, if we hit the target number exactly, return it. */
        if (currIndex == n)
            return currIndex;

        /* Otherwise, if we overshot the target number, hand back where we'd be if we
         * took one fewer step.
         */
        if (currIndex > n)
            return lastIndex;

        /* Oh well; didn't make it.  If we hit a perfect square, skip it. */
        if (currIndex == rootOfNextSquare * rootOfNextSquare)
            ++currIndex;

        ++numSmallerSquares;
        ++rootOfNextSquare;
    }
}

This optimized version of the algorithm runs in O(√N) time and uses O(1) space. The reason for the time bound is that each step of the algorithm moves to the next perfect square, and there are only O(√N) perfect squares less than N.

Hope this helps!