Daily DSA: Count Orthogonal Bitwise Pairs (Hard)
Problem Statement
You are given an integer array nums of length n.
A pair of indices (i, j) is called orthogonal if:
0 <= i < j < nnums[i] & nums[j] == 0
where & denotes the bitwise AND operator.
Return the total number of orthogonal pairs in nums.
Examples
Example 1:
Input: nums = [1, 2, 4]
Output: 3
Explanation:
The binary representations are:
- 1 = 001_2
- 2 = 010_2
- 4 = 100_2
Pair evaluations:
- (0, 1): 1 & 2 = 0
- (0, 2): 1 & 4 = 0
- (1, 2): 2 & 4 = 0
All 3 pairs have a bitwise AND equal to 0.
Example 2:
Input: nums = [0, 1, 2, 3]
Output: 4
Explanation:
The orthogonal pairs are:
- (0, 1): 0 & 1 = 0
- (0, 2): 0 & 2 = 0
- (0, 3): 0 & 3 = 0
- (1, 2): 1 & 2 = 0
Pairs (1, 3) and (2, 3) are not orthogonal because 1 & 3 = 1 and 2 & 3 = 2.
Total orthogonal pairs = 4.
Example 3:
Input: nums = [3, 5, 7]
Output: 0
Explanation:
- 3 & 5 = 1
- 3 & 7 = 3
- 5 & 7 = 5
There are no orthogonal pairs.
Constraints
1 <= nums.length <= 10^50 <= nums[i] < 2^18(i.e.,0 <= nums[i] <= 262143)
Approach
1. Algebraic Reformulation
Two numbers $x$ and $y$ satisfy $x \ \& \ y = 0$ if and only if for every bit set in $x$, the corresponding bit in $y$ is $0$. In bitmask terms, if we consider all numbers within $B = 18$ bits, $y$ must be a submask of the bitwise complement of $x$: \(y \subseteq ((2^B - 1) \oplus x)\)
Thus, for each number $x$, we need to count how many elements in nums are submasks of its complement $\sim x$.
2. Sum Over Subsets (SOS DP)
Let $freq[mask]$ be the frequency of $mask$ in nums.
We want to compute for every mask $M$:
\(F[M] = \sum_{sub \subseteq M} freq[sub]\)
A naive iteration over all submasks for each mask takes $O(3^B)$ time, which is too slow for $B = 18$ ($3^{18} \approx 3.87 \times 10^8$).
Instead, we can use SOS DP (Sum Over Subsets Dynamic Programming) which computes this prefix sum over the hypercube in $O(B \cdot 2^B)$ time:
- Iterate over each bit $i$ from $0$ to $B - 1$.
- For every mask where bit $i$ is set, add $F[mask \oplus 2^i]$ to $F[mask]$.
3. Counting Pairs and Handling Edge Cases
After computing $F[mask]$ for all $mask < 2^B$:
- For each element $x \in nums$, the number of elements $y$ such that $x \ \& \ y = 0$ is $F[\sim x]$.
- Note that if $x = 0$, $\sim x = 2^B - 1$, so $0 \subseteq \sim 0$, meaning $x = 0$ counts itself. For $x > 0$, $x$ cannot be a submask of $\sim x$ because $x \ \& \ x \ne 0$.
- Therefore, if $x == 0$, we subtract $1$ from $F[\sim x]$ to avoid pairing an element with itself.
- Sum these counts for all elements and divide by $2$ because each pair $(i, j)$ is counted twice.
C++ Source Code
#include <vector>
class Solution {
public:
long long countOrthogonalPairs(std::vector<int>& nums) {
const int B = 18;
const int MAX_VAL = 1 << B;
const int FULL_MASK = MAX_VAL - 1;
// Step 1: Count frequency of each number
std::vector<int> F(MAX_VAL, 0);
for (int x : nums) {
F[x]++;
}
// Step 2: Sum Over Subsets (SOS) DP
for (int i = 0; i < B; ++i) {
for (int mask = 0; mask < MAX_VAL; ++mask) {
if (mask & (1 << i)) {
F[mask] += F[mask ^ (1 << i)];
}
}
}
// Step 3: Count total matching pairs
long long total_matches = 0;
for (int x : nums) {
int comp = FULL_MASK ^ x;
long long valid_candidates = F[comp];
// An element can only pair with itself if x & x == 0 (which means x == 0)
if (x == 0) {
valid_candidates--;
}
total_matches += valid_candidates;
}
// Each unordered pair (i, j) was counted twice (once for i, once for j)
return total_matches / 2;
}
};
Complexity Analysis
- Time Complexity: $O(n + B \cdot 2^B)$, where $n$ is the size of
numsand $B = 18$.- Frequency count: $O(n)$.
- SOS DP transitions: $18 \times 2^{18} \approx 4.7 \times 10^6$ operations, which easily runs in $\approx 20$ ms.
- Final summation: $O(n)$.
- Overall runtime is well within the 1-second limit.
- Space Complexity: $O(2^B)$ auxiliary space for the DP array
F, which requires $2^{18} \times 4$ bytes $\approx 1\text{ MB}$ of memory.