劃分等於異或數組

我不知道如何去了解這個問題>>劃分等於異或數組

鑑於整數數組，我們需要的是陣列分爲兩個部分，使得

1）XOR第一組相等於第二組

2）兩部分元素之和的差異最大。

例如：

如果給定的數組是[4,2,6]

話，就可以分成[2]，[4,6]，

  where xor(2) = 010 
       xor(4,6) = 100^110 = 010 = xor(2)

和兩部分之和的差值=（4 + 6）-2 = 8（滿足上述約束條件的最大可能差值）。

（如果不是第二個約束，將數組分成相等的部分就足夠了）。

來源

2013-08-22 saikiranboga

我不確定分割本身是否簡單。樣本：數組是'[687,4,984,29,3927,93,3]'和？如何以簡單的方式分割這個？（你在這裏有很多分區，從具有一個元素的組開始） –

我們可以看到，爲了以這種方式分割數組，整個數組的xor必須是0 – saikiranboga

這是個詭異的問題。

如果您有整數a1 ... an，並且可以將它們分成兩部分，使得它們的XOR相等，這只是表示a1 xor a2 xor ... xor an等於零。如果這樣，任何分區都可以工作，例如（a1）xor（a2 xor a3 xor ... xor an）== 0，所以它必須是a1 == a2 xor ... xor an。因此，任何分區的作品。鑑於此，您只需選擇一個空分區和完整分區（如果允許的話），或者將最小整數分配到一個單獨分區中，並將其他所有分區放入第二個分區中。

來源

2013-08-22 10:55:13

劃分等於異或數組

回答

相關問題