数的异或=X

Question

样本输入:n=3,x=2

示例输出：1 1 2

说明：我们必须打印3个具有最小和的自然数，因此n间隔的数是[1，1，2]

有人知道如何使数组和最小吗？

Answer 1

为了得到最小的总和，您需要确保当您的目标是X时，您不会取消X的位并重新创建它们。因为这样会增加总和。为此，您已经从数组的末尾一个接一个地创建了X的位（理想情况下）。因此，在n=4和x=6的示例中，我们有：（我使用^来表示xor）

x=7=110（二进制）=2+4。请注意，2^4=6，因为这些数字不共享任何公共位。所以，输出是1 1 2 4。

因此，我们从创建输出数组末尾X的最高有效位开始。然后，我们还必须处理不同N值的转角情况。我将用一些不同的例子来说明这一点：

``
 A) X=14, N=5:
    X=1110=8+4+2. So, the array is 1 1 2 4 8.
 B) X=14, N=6:
    X=8+4+2. The array should be 1 1 1 1 2 12.
 C) X=15, N=6:
    X=8+4+2+1. The array should be 1 1 1 2 4 8.
 D) X=15, N=5:
    The array should be 1 1 1 2 12.
 E) X=14, N=2:
   The array should be 2 12. Because 12 = 4^8
``