数组中满足位方程的对数

Question

我在一次比赛中发现了这个问题。问题是：

给你一个 N 非负整数数组 (A1, A2, A3,..., An) 和一个整数 M.您的任务是找到满足以下按位方程的无序数组元素对的数量 (X,Y)：

2 * set_bits(X|Y) = M + set_bits(X ⊕ Y)

注：

• set_bits(n)表示一个整数的二进制表示中1的个数n.
• X|Y表示整数X和Y.
按位或
• X ⊕ Y表示整数X和Y.
按位异或
• 数组元素的无序对是对 (Ai, Aj) 其中 1 ≤ i < j ≤ N.

打印满足上述按位方程的无序数组元素对的数量。

1. 示例输入 1：
   N=4 M=2
   arr = [3, 0, 4, 5]
   示例输出：2
   2对是(3,0)和(0,5)

2. 示例输入 2：
   N=8 M=2
   arr = [3, 0, 4, 5, 6, 8, 1, 8]
   示例输出：9

除了brute force还有其他解方程的方法吗？

Answer 1

如果set_bits的时间复杂度为O(1)，则存在时间复杂度为O(n)的解。

首先，我们要重新表述一下条件（按位方程）。假设给定一对元素(X, Y)。令c_01表示X为0而Y为1的位数，c_10表示X为1，Y为0的位数，c_11表示其中的位数X和Y为1。例如，当X=5和Y=1时（X=101，Y=001），c_01 = 0，c_10 = 1，c_11 = 1。现在，条件可以改写为

2 * (c_01 + c_10 + c_11) = M + (c_01 + c_10)

因为 set_bits(X|Y) 等于 c_01 + c_10 + c_11 而 set_bits(X^Y) 等于 c_01 + c_10。 我们可以将等式重新排序为

c_01 + c_10 + 2*c_11 = M

通过将右侧的术语移动到左侧。现在，意识到 set_bits(X) = c_10 + c_11。将此信息应用于我们得到的等式

c_01 + c_11 = M - set_bits(X)

现在，也意识到set_bits(Y) = c_01 + c_11。等式变为

set_bits(Y) = M - set_bits(X)

或

set_bits(X) + set_bits(Y) = M

问题变成了计算第一个元素中设置位的数量加上第二个元素中设置位的数量等于 M 的对数。这可以在线性时间内完成，假设您可以在恒定时间内计算 set_bits。