algorithm - 反复消除完美平方后剩下多少？

Question

我在Topcoder中练习SRM问题。我遇到了这个问题
问题陈述：今天是平安夜。全世界的人
庆祝这个节日。下面的故事发生在
驯鹿，圣诞老人居住的地方。
驯鹿喜欢糖果。他们有N块糖果。碎片
糖果的编号是1到N。达舍是驯鹿之一。他
想吃一个糖果。去挑他要吃的，达舍
使用以下方法：当存在多个
糖果：丢弃所有用完美方块编号的糖果（即，
糖果1、4、9、16、25等）。重新标记剩余的K糖果1
通过k，保持数字的顺序不变。一次只有一件
剩下的糖果，达舍会吃的。
给你一个整数。你的方法必须计算并返回这个数字
最初分配给Dasher吃的糖果。
我使用ARAYLIST解决了这个问题，但是我的解决方案对于非常大的数字失败（Java堆SabCE异常）。因此，我在思考是否有可能解决O（1）空间复杂度的问题。
请给出你的建议和方法。我不希望代码只解释解决这个问题的逻辑。
我已经用问题的陈述重新打开了这个问题，以使我能在O（1）空间复杂性中帮助我解决这个问题。

Answer 1

我相信下面的解决方案是正确的，并且使用了o（1）内存，假设您可以在o（1）空间中保存一个整数。我们的想法是尝试反向运行这个过程，直到找到正确糖果的最终位置。
让我们来追踪这个问题的一个例子，其中n=10。然后我们得到这个：

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

现在，假设我们要计算这个问题的最终结果。我们知道吃完后，吃的糖果在第一位，因为只剩下一块糖果了。所以我们试着这样设置：

1

现在，我们知道在上一次迭代中，索引1处的糖果一定被吃掉了。这意味着最后的糖果实际上是在第二位：

?   2

在这之前的迭代中，我们知道自从Candy 1被吃掉之后，我们的Candy一定在位置3：

?   ?   3

此时，我们再次回顾一次迭代。我们知道糖果1被吃掉了，但是糖果4也被吃掉了。这意味着，在上一次迭代中，糖果的索引必须是5，因为当我们将它移到正确的位置时，它必须跳过第一个元素的一个位置和第四个元素的一个位置：

?   ?   ?   ?   5

重复同样的逻辑，我们得到上一个索引应该是7：

?   ?   ?   ?   ?   ?   7

现在，下一步，我们知道我们会把糖果挪到两个位置，因为我们去掉了第1和第4个元素。然而，这将把我们的糖果放在位置9，这将被删除。这意味着我们要把糖果放在第10位：

?   ?   ?   ?   ?   ?   ?   ?   ?   10

在这一点上，由于还有10个糖果，我们知道，我们已经完全扭转了这一过程，并已完成。因为我们糖果的最后一个休息点是位置10，我们知道答案是，第10个糖果是被吃掉的，这完全符合我们之前的工作！
这种方法背后的诀窍是，我们不需要太多的内存来让它工作。特别是，在每一步中，我们只需要跟踪一些事情：
最后一块糖果的指数是多少？我们需要这个来知道停在哪里。
指数下面有多少个正方形？我们需要知道每一步有多少元素被删除。
下一个完美的正方形是什么？我们需要知道每次被删除的方块数何时增加。
我们最后一次探索的索引是什么？这个算法通过向后运行进程来工作，所以在某个时刻我们会意识到我们已经运行了一次太多了。当这种情况发生时，我们需要能够“备份”一个步骤，以获得最后一个没有超调的索引。
鉴于此，我们有以下算法：
将当前索引设置为1。
将较小的完美正方形数设置为1。
将下一个完美正方形设置为4。
将最后一个较小的索引设置为1。
当当前索引小于n时：
将最后一个较小的索引设置为当前索引（请记住目前的解决方案）。
设置当前索引+=较小的完美正方形的数目（将进程向后运行一步）
如果当前索引等于下一个完美正方形，则在其上添加一个（向后运行该索引的边沿情况；如果遇到完美正方形，则应超过它一步）
如果当前索引大于下一个完美正方形（现在每个步骤删除的数字更多）：
将完美的正方形设置为下一个完美的正方形。
在小于索引的完美正方形数上加一个。
返回最后一个较小的索引。
这只需要O（1）内存来保存所有值。
我们来举个例子吧！当n=20时，如果我们通过正式的过程，我们得到：

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

如果我们运行我们的算法，我们得到

 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

因为21>20，最后一个较小的索引是17，所以我们返回17，这是正确的答案！
编写为C代码，假设没有整数溢出：

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;
}

然而，如前所述，该算法不是特别有效。具体来说，在n=20的例子中看看它的行为。请注意，我们有三个回合，其中步长为1，步长为2和3的是2，等等。我们可以不显式地进行这些回合，而是计算用该步长必须进行的回合数，然后一次运行所有这些步骤。这样，我们总是有一轮一号，一轮二号，一轮三号，等等。要做到这一点，在每一步我们都需要看看我们的下一个目标是什么；这要么是数字n，要么是下一个完美的正方形。一旦我们找到了目标，我们需要看看需要多少步骤才能达到目标。如果当前索引是i，目标是t，如果步长是k，则需要采取（t-i）/k步骤才能达到目标。使用一个整数除法的小技巧，我们可以将其计算为

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

这为我们提供了以下更新算法：

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;
    }
}

优化后的算法运行在o（√n）时间内，使用o（1）空间。之所以有时间限制，是因为算法的每一步都会移动到下一个完美平方，并且只有o（√n）个完美平方小于n。
希望这有帮助！