Sum of Pairwise ANDs

Problem Overview

Summing AND over all pairs looks quadratic, but each bit position contributes independently.

Intuition

Summing AND over all pairs looks quadratic, but each bit position contributes independently. Bit b appears in the final sum only when both numbers in a pair have that bit set. Count how many array values have bit b, then every pair among them adds 2^b.

Algorithm

1Initialize ans = 0.
2For each bit b from 0 to 30, count elements with that bit set.
3Pairs with both bits set: count * (count - 1) / 2.
4Add pairs * (1L << b) to ans.
5Return ans.

Example Walkthrough

Input: arr = [5, 10, 15]

1. Pairs: 5&10=0, 5&15=5, 10&15=10.
2. Bit 0: two numbers set, one pair, adds 1.
3. Bit 2 and bit 3 each add one pair worth 4 and 8.
4. Total 0 + 5 + 10 = 15.

Output: 15

Common Pitfalls

• Use long for counts and the answer; pair products grow quickly.
• Check 31 bit positions for typical GFG int inputs.
• Do not enumerate all n choose 2 pairs when bit counting is enough.
• Each unordered pair i < j is counted once in the bit formula.

Sum of Pairwise ANDs.java

Java

// Approach: AND is independent per bit. Count how many numbers have bit b set.
// Each such pair contributes 2^b, so add C(count,2) * (1 << b) for every bit.
// Complexity: O(31 * n) time and O(1) extra space.
class Solution {

    public long pairAndSum(int[] arr) {
        long ans = 0;

        for (int bit = 0; bit < 31; bit++) {
            long count = 0;

            for (int x : arr) {
                if ((x & (1L << bit)) != 0) {
                    count++;
                }
            }

            long pairs = count * (count - 1) / 2;
            ans += pairs * (1L << bit);
        }

        return ans;
    }
}

Was this solution helpful?