数字的XOR = X

Question

我在一次招聘竞赛中发现了这个问题（现已结束）。这里是：

给您两个自然数N和X。您需要创建一个由N个自然数组成的数组，以使这些自然数的按位XOR等于X。该数组中所有可用自然数的总和为最小值尽可能。

如果存在多个数组，则打印最小的数组

如果
任何索引i的A [i] <B [i]，并且对于所有小于i的索引，A [i] = B [i]，则数组A <数组B

样本输入：N = 3，X = 2

样本输出：1 1 2

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

我的方法：如果N为奇数，则将N-1放入数组中（以使它们的xor为零），然后将X放入

如果N是偶数，我会再次放N-1，然后再放X-1（如果X是奇数）和X + 1（如果X是偶数）

但是该算法在大多数测试用例中均失败。例如，当N = 4和X = 6时，我的输出是，
1 1 1 7但应该是1 1 2 4

有谁知道如何使数组总和最小？

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
``

因此，我们进行如下操作。我们计算X的2的幂。让这个数为k。

情况1-如果k <= n（示例E）：我们从左到右选取最小的幂，然后将剩余的幂合并到数组的最后一个位置。

情况2-如果k> n（示例A，B，C，D）：我们计算h = n-k。如果h是奇数，我们将h = n-k + 1。现在，我们将h 1放入数组的开头。然后，剩余的位数少于k。因此，对于其余职位，我们可以遵循案例1的想法。请注意，在情况2中，我们放置的不是奇数个加1的数字，而是有偶数个1的数字，然后在最后进行合并。这样可以保证数组是最小的。