数字的异或 = X

Question

我在一次招聘比赛中遇到了这个问题(现在已经结束了)。具体如下:

给定两个自然数N和X。你需要创建一个由N个自然数组成的数组，使得这些数字的位异或等于X。可用的自然数的总和应尽可能地小。

如果存在多个数组，则输出最小的一个。

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

示例输入: N=3, X=2

示例输出 : 1 1 2

说明: 我们必须打印出三个自然数，使其总和最小。因此N空间数字是[1 1 2]

我的方法是: 如果N是奇数，我将N-1个1放入数组中(使它们的异或为零)，然后再放入X

如果N是偶数，我再次放入N-1个1，然后将X-1(如果X是奇数)和X+1(如果X是偶数)放入数组中

但是这种算法在大多数测试用例中都不成功。例如，当N=4且X=6时，我的输出为
1 1 1 7，但正确答案应该是1 1 2 4

有人知道怎样使数组的总和最小吗?

- Klasen

---

为什么要用X-1或X+1而不是X？另外，请确保允许零。 - Nico Schertler

@NicoSchertler 我们必须使用自然数。因此，我们不能使用零。 我使用X-1和X+1，因为当N是偶数时，N-1将是奇数，因此会留下一个“1”，我们必须使1 xor Y = X，因此Y = X-1或X+1。 - Klasen

这与您在问题中所写的“我放了N-1个零”相矛盾...此外，是否将零视为自然数还有争议。 - Nico Schertler

@NicoSchertler 抱歉，那是错误操作。你不能使用 1 (已编辑)。 - Klasen

@NicoSchertler 当N=4且X=6时， 我的输出是1 1 1 7， 但应该是1 1 2 4。 - Klasen

Answer 1

为了使和最小，需要确保在目标值X时，不要取消X的位并重新创建它们，因为这会增加总和。为此，您需要从数组末尾开始逐个创建X的位（理想情况下）。例如，当N=4且X=6时，我们有：(我使用^表示异或) 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，然后在最后进行一些合并操作。这保证了数组的大小最小化。

- A. Mashreghi

Answer 2

我们必须考虑到需要最小化数组的和才能得到解决方案，这是关键点。 首先，计算N中的集位数。如果集位数小于或等于X，则将N分成基于集位的X个整数。

例如： N = 15，X = 2 15的集位数是4，那么解决方案就是1 14 如果X = 3，则解决方案为1 2 12，这也能最小化数组和。

另一种情况是，如果集位大于X， 计算差值=集位（N）- X。 如果差值是偶数，则根据需要添加1，并且应用以上算法。所有1都会抵消掉。 如果差值是奇数，则添加1，但现在你必须考虑答案数组中多出来的1。还要检查极端情况。

- Arjun Singh