时间戳

首页 > 解决方案 > 数组中满足位方程的对数

algorithm - 数组中满足位方程的对数

问题描述

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

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

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

笔记：

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

  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除了解这个方程还有其他方法吗？

标签： algorithmbit-manipulationxor

解决方案

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

首先，我们将稍微改写一下条件（按位方程）。假设给定一对元素(X, Y)。令c_01表示X为0但Y为1c_10的位数，表示X为1且Y为0c_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假设您可以在恒定时间内进行计算，这可以在线性时间内完成。

推荐阅读