algorithm - 数字异或 = X

Question

我在招聘竞赛中发现了这个问题(现已结束)。在这里:

给定两个自然数 N 和 X。你需要创建一个包含 N 个自然数的数组，使得这些数字的按位异或等于 X。数组中所有可用自然数的总和尽可能少。

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

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

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

示例输出:1 1 2

解释:我们必须打印 3 个具有最小总和的自然数，因此 N 间隔的数字是 [1 1 2]

我的方法: 如果 N 是奇数，我将 N-1 个放入数组中(以便它们的异或为零)然后放入 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 也是因为这些数字不共享任何公共(public)位。所以，输出是 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，然后在最后进行一些合并。这保证了数组是最小的。