The Number of Perfect Pairs problem defines a "perfect pair" as two indices (i, j) where i < j and arr[i]^arr[j] == arr[i] + arr[j]. The XOR equals the sum only when there's no carry in binary addition — meaning no bit position has 1s in both numbers. This is equivalent to arr[i] & arr[j] == 0. Count all such pairs. This coding problem uses sorting with two pointers or hash map counting.
Goldman Sachs and Squarepoint Capital ask this because it requires recognizing the mathematical condition a XOR b == a + b ⟺ a AND b == 0. Once this insight is recognized, pair counting with a hash map or sorting is straightforward. The array, math, sorting, and two pointers interview pattern is applied.
Hash map frequency counting. For each pair (a, b) where a & b == 0, count them as a perfect pair. For each element a, count elements b where (a & b) == 0. A simple O(n²) check works for small inputs. For larger inputs, iterate over all possible complements. Use frequency map to count pairs efficiently.
Array: [1,2,4,8]. Binary: 0001, 0010, 0100, 1000.
Array: [1,3,5]: 1&3=01&11=01≠0. 1&5=001&101=001≠0. 3&5=011&101=001≠0. Answer = 0.
a XOR b == a + b implies a AND b == 0.The identity a XOR b == a + b ⟺ a AND b == 0 is a key bit manipulation insight — XOR represents addition without carry, so no carry ⟺ no common bits. Memorize this equivalence. For counting pairs with a & b == 0, sort the array and use the "submask enumeration" technique for high-performance solutions on larger inputs. Practice converting XOR/sum conditions to AND conditions systematically.
| Title | Difficulty | Topics | LeetCode |
|---|---|---|---|
| Sort Transformed Array | Medium | Solve | |
| Sort Array By Absolute Value | Easy | Solve | |
| Rotate Array | Medium | Solve | |
| Sort Colors | Medium | Solve | |
| 3Sum | Medium | Solve |