Sum By OR
Source: codechef
Difficulty: 2308

Sum By OR
Let$f(X, Y) = \left \lceil \dfrac{X + Y}{X | Y} \right \rceil$, i.e. the result of$X + Y$divided by$X | Y$rounded up, where$|$denotes the Bitwise OR symbol.
You are given an array$A$of length$N$.
Your task is to compute$\sum_{i = 1}^{N} \sum_{j = i + 1}^{N} f(A_i, A_j)$, i.e. the sum of$f$over all pairs in the array$A$.
Note
: There is an additional constraint on the input that every number has at most$4$bits set
in their binary representation, i.e. it is possible to write$A_i = 2^{X_1} + 2^{X_2} + ... + 2^{X_L}$with$L \le 4$and$X_i$are all non-negative integers.
Input Format
The first line of input will contain a single integer$T$, denoting the number of test cases.
Each test case consists of multiple lines of input.
The first line contains$N$- the size of the array.
The second line contains$N$integers -$A_1, A_2, ...., A_N$.
Output Format
For each test case, output on a new line the value of$\sum_{i = 1}^{N} \sum_{j = i + 1}^{N} f(A_i, A_j)$.
Constraints$1 \le T \le 10^4$$2 \le N \le 2 \cdot 10^5$$1 \le A_i \lt 2^{30}$$A_i$can be written as$2^{X_1} + 2^{X_2} + .... + 2^{X_L}$with$L \le 4$and$X_i$non-negative integers.
The sum of$N$does not exceed$2 \cdot 10^5$over all test cases.
Sample 1:
Explanation:
Test Case 1
: There is only one pair in the array$i = 1, j = 2$. So, we need to evaluate$f(1, 2) = \lceil \frac{3}{3} \rceil = 1$, as$1 + 2 = 1 | 2 = 1$.
Test Case 2
: It can be shown that$f(1, 1) = 2$, and there are$3$such pairs. Hence, the answer is$3 \cdot 2 = 6$.

Sample Input:
2
2
1 2
3
1 1 1

Sample Output:
1
6

C++ solution:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

int main() {
    int x;
    cin >> x;
    while (x--) {
        int y;
        cin >> y;
        vector < int > z(y);
        for (int i = 0; i < y; i++) cin >> z[i];
        unordered_map < int, int > xy;
        xy.reserve(y * 2);
        for (auto v: z) xy[v]++;
        ll yz = (ll) y * (y - 1) / 2;
        vector < pair < int, int >> xz;
        xz.reserve(xy.size());
        for (auto & p: xy) xz.pb({
            p.first,
            p.second
        });
        unordered_map < int, ll > zy;
        for (auto & p: xz) {
            int noob = p.first;
            int cnt = p.second;
            vector < int > zz;
            for (int i = 0; i < 31; i++)
                if (noob & (1 << i)) zz.pb(i);
            int k = zz.size();
            int val = (1 << k);
            for (int mask = 1; mask < val; mask++) {
                int sub = 0;
                for (int j = 0; j < k; j++)
                    if (mask & (1 << j)) sub |= (1 << zz[j]);
                zy[sub] += cnt;
            }
        }
        ll ans = 0;
        for (auto & p: zy) {
            ll cnt = p.second;
            if (__builtin_popcount(p.first) & 1) ans += cnt * (cnt - 1LL) / 2;
            else ans -= cnt * (cnt - 1LL) / 2;;
        }
        cout << yz + ans << "\n";
    }
    return 0;
}

Go solution:
package main

import (
    "bufio"
    "fmt"
    "os"
)

const maxBits = 30

func pairKey(i, j int) int { return (i << 5) | j }
func tripleKey(i, j, k int) int { return (i << 10) | (j << 5) | k }
func quadKey(i, j, k, l int) int { return (i << 15) | (j << 10) | (k << 5) | l }

func processBits(x int64, bits *[]int) {
    *bits = (*bits)[:0]
    for p := 0; p < maxBits; p++ {
        if x&(1<<p) != 0 {
            *bits = append(*bits, p)
        }
    }
}

func updateFrequencies(bits []int, freqBit []int64, freqBitPair [][]int64, freqBitTriple, freqBitQuad, freqSet map[int]int64) {
    sz := len(bits)
    if sz == 0 {
        return
    }

    var mask int64
    for _, p := range bits {
        mask |= 1 << p
    }
    freqSet[int(mask)]++

    for _, b := range bits {
        freqBit[b]++
    }
    if sz >= 2 {
        for i1 := 0; i1 < sz; i1++ {
            for i2 := i1 + 1; i2 < sz; i2++ {
                freqBitPair[bits[i1]][bits[i2]]++
            }
        }
    }
    if sz >= 3 {
        for i1 := 0; i1 < sz; i1++ {
            for i2 := i1 + 1; i2 < sz; i2++ {
                for i3 := i2 + 1; i3 < sz; i3++ {
                    key := tripleKey(bits[i1], bits[i2], bits[i3])
                    freqBitTriple[key]++
                }
            }
        }
    }
    if sz == 4 {
        key := quadKey(bits[0], bits[1], bits[2], bits[3])
        freqBitQuad[key]++
    }
}

func calculateSumInt(bits []int, freqBit []int64, freqBitPair [][]int64, freqBitTriple, freqBitQuad map[int]int64) int64 {
    var sumInt int64
    sz := len(bits)

    for sub := 1; sub < (1 << sz); sub++ {
        popcount := 0
        for i := 0; i < sz; i++ {
            if sub&(1<<i) != 0 {
                popcount++
            }
        }
        var v []int
        for bpos := 0; bpos < sz; bpos++ {
            if sub&(1<<bpos) != 0 {
                v = append(v, bits[bpos])
            }
        }
        var val int64
        if popcount == 1 {
            val = freqBit[v[0]]
        } else if popcount == 2 {
            val = freqBitPair[v[0]][v[1]]
        } else if popcount == 3 {
            key := tripleKey(v[0], v[1], v[2])
            val = freqBitTriple[key]
        } else {
            key := quadKey(v[0], v[1], v[2], v[3])
            val = freqBitQuad[key]
        }
        if popcount%2 == 1 {
            sumInt += val
        } else {
            sumInt -= val
        }
    }
    return sumInt
}

func solve() {
    scanner := bufio.NewScanner(os.Stdin)
    scanner.Split(bufio.ScanWords)

    scanner.Scan()
    T := atoi(scanner.Text())
    for t := 0; t < T; t++ {
        scanner.Scan()
        N := atoi(scanner.Text())

        freqBit := make([]int64, maxBits)
        freqBitPair := make([][]int64, maxBits)
        for i := range freqBitPair {
            freqBitPair[i] = make([]int64, maxBits)
        }
        freqBitTriple := make(map[int]int64)
        freqBitQuad := make(map[int]int64)
        freqSet := make(map[int]int64)

        for i := 0; i < N; i++ {
            scanner.Scan()
            x := atoi64(scanner.Text())
            var bits []int
            processBits(x, &bits)
            updateFrequencies(bits, freqBit, freqBitPair, freqBitTriple, freqBitQuad, freqSet)
        }

        nN := int64(N)
        var disjointPairs int64

        for mask, count := range freqSet {
            if count == 0 {
                continue
            }
            var bits []int
            for p := 0; p < maxBits; p++ {
                if mask&(1<<p) != 0 {
                    bits = append(bits, p)
                }
            }
            sumInt := calculateSumInt(bits, freqBit, freqBitPair, freqBitTriple, freqBitQuad)
            disj := nN - sumInt
            disjointPairs += count * disj
        }
        disjointPairs /= 2
        ans := (nN * (nN - 1)) - disjointPairs
        fmt.Println(ans)
    }
}

func atoi(s string) int {
    i := 0
    for _, c := range s {
        i = i*10 + int(c-'0')
    }
    return i
}

func atoi64(s string) int64 {
    var i int64
    for _, c := range s {
        i = i*10 + int64(c-'0')
    }
    return i
}

func main() {
    solve()
}

Java solution:
import java.io.*;
import java.util.*;

class Codechef {
    public static void main(String[] args) throws java.lang.Exception {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter w = new PrintWriter(System.out);
        int t = Integer.parseInt(r.readLine());

        while (t-- > 0) {
            int n = Integer.parseInt(r.readLine());
            String[] s = r.readLine().split(" ");
            int[] a = new int[n];

            for (int i = 0; i < n; i++) {
                a[i] = Integer.parseInt(s[i]);
            }

            HashMap<Integer, Long> h = new HashMap<>();

            for (int i = 0; i < n; i++) {
                int x = a[i];
                ArrayList<Integer> l = new ArrayList<>();

                for (int j = 0; j < 30; j++) {
                    if ((x & (1 << j)) != 0) {
                        l.add(j);
                    }
                }

                int k = l.size(), u = 1 << k;

                for (int p = 1; p < u; p++) {
                    int m = 0;

                    for (int q = 0; q < k; q++) {
                        if ((p & (1 << q)) != 0) {
                            m |= 1 << l.get(q);
                        }
                    }

                    h.put(m, h.getOrDefault(m, 0L) + 1);
                }
            }

            long c = 0;

            for (Map.Entry<Integer, Long> e : h.entrySet()) {
                int m = e.getKey();
                long f = e.getValue();

                if (f >= 2) {
                    int o = Integer.bitCount(m);
                    long p = f * (f - 1) / 2;
                    if ((o & 1) == 1) {
                        c += p;
                    } else {
                        c -= p;
                    }
                }
            }

            long z = (long) n * (n - 1) / 2;
            long d = z + c;
            w.println(d);
        }

        w.flush();
        w.close();
    }
}

JavaScript solution:
function solve() {
    const fs = require("fs");
    const inputData = fs.readFileSync(0, "utf-8").trim().split(/\s+/);
    if (!inputData.length) return;

    let testCases = parseInt(inputData[0]);
    let index = 1;
    let outputLines = [];

    for (let t = 0; t < testCases; t++) {
        let n = parseInt(inputData[index]);
        index += 1;
        let arr = inputData.slice(index, index + n).map(Number);
        index += n;

        let totalPairs = (n * (n - 1)) / 2;
        let subsetCount = new Map();

        for (let num of arr) {
            let bits = [];
            let temp = num;
            let position = 0;

            while (temp) {
                if (temp & 1) {
                    bits.push(position);
                }
                temp >>= 1;
                position += 1;
            }

            let k = bits.length;
            for (let mask = 1; mask < (1 << k); mask++) {
                let s = 0;
                let b = 0;
                let tempMask = mask;

                while (tempMask) {
                    if (tempMask & 1) {
                        s |= (1 << bits[b]);
                    }
                    tempMask >>= 1;
                    b += 1;
                }
                subsetCount.set(s, (subsetCount.get(s) || 0) + 1);
            }
        }

        let intersections = 0;
        for (let [m, cnt] of subsetCount.entries()) {
            if (cnt >= 2) {
                let sign = (m.toString(2).split('1').length - 1) % 2 === 1 ? 1 : -1;
                intersections += sign * (cnt * (cnt - 1)) / 2;
            }
        }

        let ans = totalPairs + intersections;
        outputLines.push(ans.toString());
    }

    console.log(outputLines.join("\n"));
}

solve();

Python solution:
# cook your dish here
def solve():
    import sys,sys
    data = sys.stdin.read().strip().split()
    if not data: 
        return
    t = int(data[0])
    index = 1
    out_lines = []
    
    # cache for a given number to its list of nonempty subset masks
    subset_cache = {}
    
    # helper: given a number a, return list of all nonempty subset masks of its set bits.
    def get_subsets(a):
        # if already computed, return cached value
        if a in subset_cache:
            return subset_cache[a]
        bits = []
        # get positions of set bits (0-indexed)
        pos = 0
        x = a
        while x:
            if x & 1:
                bits.append(pos)
            pos += 1
            x //= 2
        n_bits = len(bits)
        subsets = []
        # iterate over all nonempty submasks of the bits list (range: 1 to (1<<n_bits)-1)
        for mask in range(1, 1 << n_bits):
            s = 0
            bit_index = 0
            m = mask
            while m:
                if m & 1:
                    s |= 1 << bits[bit_index]
                bit_index += 1
                m //= 2
            subsets.append(s)
        subset_cache[a] = subsets
        return subsets

    # Process each test case
    for _ in range(t):
        n = int(data[index])
        index += 1
        arr = list(map(int, data[index:index+n]))
        index += n
        
        total_pairs = n*(n-1)//2
        cnt = {}
        
        # For each number, update counts for all nonempty subsets of its set bits.
        for a in arr:
            subs = get_subsets(a)
            for s in subs:
                cnt[s] = cnt.get(s, 0) + 1
        
        non_disjoint = 0
        # For each subset s, add its contribution using inclusion-exclusion.
        # sign = 1 if popcount(s) is odd, -1 if even.
        for s, freq in cnt.items():
            if freq < 2:
                continue
            # Using Python 3.10+ built-in popcount: s.bit_count()
            sign = 1 if (s.bit_count() & 1) == 1 else -1
            non_disjoint += sign * (freq*(freq-1)//2)
        
        # Final answer is total_pairs + non_disjoint.
        ans = total_pairs + non_disjoint
        out_lines.append(str(ans))
    
    sys.stdout.write("\n".join(out_lines))
    
if __name__ == '__main__':
    solve()

Ruby solution:
def solve
  input = $stdin.read.split
  ptr = 0
  test_cases = input[ptr].to_i
  ptr += 1
  test_cases.times do
    n = input[ptr].to_i
    ptr += 1
    a = input[ptr, n].map(&:to_i)
    ptr += n

    freq = Hash.new(0)
    ans = 0
    a.each do |x|
      sub = x
      while sub > 0
        if sub.to_s(2).count('1') % 2 == 0
          ans -= freq[sub]
        else
          ans += freq[sub]
        end
        freq[sub] += 1
        sub = (sub - 1) & x
      end
    end
    total_pairs = n * (n - 1) / 2
    puts ans + total_pairs
  end
end

solve