Different Bits Sum Pairwise

题目描述

We define f(X, Y) as number of different corresponding bits in binary representation of X and Y. For example, f(2, 7) = 2, since binary representation of 2 and 7 are 010 and 111, respectively. The first and the third bit differ, so f(2, 7) = 2.

You are given an array of N positive integers, A1, A2 ,…, AN. Find sum of f(Ai, Aj) for all pairs (i, j) such that 1 ≤ i, j ≤ N.

解题方法

brute force

求每一个pairt, o(n^2)

O(n)的方法

因为是求bit的different, 每一个bit我们可以独立的来看。 可以发现最后的结果可以分解成32个bit的和。

我们可以通过遍历找出每一位有多少数字为0，有多少数字为1，它们两两都可以 成对。假设有10个数，在第1个bit上有6个为0，4个位1，那么第一位bit的differnt bits sum pairwise的结果就是6 * 4 * 2

所以求每一位bit为0和为1的数的个数，然后将32位bit的结果加起来。

Solution

class Solution:
    # @param A : list of integers
    # @return an integer
    def cntBits(self, A):
        result = 0
        length = len(A)
        for i in range(32):
            set_count = 0
            bitmask = 1 << i
            for num in A:
                if (num & bitmask) != 0:
                    set_count += 1
            result += set_count * (length - set_count) * 2

        return result

Reference

• geeksforgeeks