求将数组所有元素变为相等的最小XOR操作次数

给定一个长度为N的整数数组A，我们需要通过选择任意元素，将其与2^x（x≥0，即2的非负整数次幂）执行按位异或操作，用最少的操作次数让数组所有元素变得相等。最终返回这个最小操作次数。

操作说明 #

每次异或2^{x，本质是翻转该元素二进制表示中的第x位（因为2}x的二进制只有第x位为1，异或后该位0变1、1变0）。因此，把一个元素变成目标值target的操作次数，等于该元素与target二进制中不同位的数量。

示例 #

• 示例1：数组A={10,1,4,2}，最小操作次数为5
• 示例2：数组A={5,7,4,3,5}，最小操作次数为4

解题思路 #

要得到总操作次数的最小值，核心是找到一个最优目标值target，使得数组中所有元素与target的二进制不同位数量之和最小。具体步骤如下：

1. 统计数组中每个元素二进制每一位（从第0位到最高位）上0和1的出现次数
2. 对每一位单独计算：如果该位有c个0、(N-c)个1，那么选择最终该位为0时需要翻转(N-c)次，选择为1时需要翻转c次，取两者中的较小值
3. 将所有位的最小翻转次数相加，得到的总和就是答案

内容的提问来源于stack exchange，提问作者Ajay jangid