algorithm - 找到对整数数组进行异或以产生零的全部方法

Question

如果我们有一个整数数组，那么我们如何找到对它们进行异或以使结果为 0 的方式数。这里，在每一步中，只有一个整数(i)可以减少任意数量，例如d，使得(i-d)>=0。例如，对于整数 11,15,8，我们可以将 11 减少到 7，这样 7^15^8 =0 。类似地，15 可以减少到 3，这样 11^3^8 = 0 和 8 可以减少到 4，这样 11^15^4=0 。因此总共有 3 种方式

我的方法:对于每个整数，继续减少它，并在每一步将其与数组中剩余的整数进行异或，如果结果为 0 ，则中断。检查所有整数并获取总方法。但这是 0(n^2) 。有什么有效的方法可以做到吗？ 谢谢。

Answer 1

您可以对数组中的所有整数进行异或，然后在循环中将结果与每个整数进行异或(它将从所有整数中“删除”该整数，因为 x^x 始终为 0)。结果，您将得到其他成员的 XOR，这就是要替换的数字(因为 x^x 始终为 0)。

    int[] a = new int [size];
    //initialize 'a' array
    int[] b = new int [size];
    int all = 0;
    for(int i = 0; i<a.length; i++)
        all=all^a[i];

    for(int i =0; i< size; i++)
        b[i] = all^a[i];

在 b[i] 中，您将得到需要用 a[i] 替换的数字以获得零。
我编辑了我的答案并尝试了，它有效。这是 O(n)。