Frontend School

Bit Swap Anagram Pairs

DSA
medium

Bit Swap Anagram Pairs

Medium
Bit Manipulation
Hash Map
Combinatorics

Overview

In many data-driven applications, understanding the structural similarity between binary representations of numbers can be crucial. For instance, in feature engineering or anomaly detection, identifying data points that are just a "single bit-swap away" from each other might reveal interesting relationships or potential errors. This problem challenges you to find such structurally similar pairs efficiently.

What you need to do / Task

Implement the function countBitSwapAnagramPairs that takes an array of non-negative integers nums. Your task is to count the number of distinct pairs of indices (i, j) such that i < j and nums[i] can be transformed into nums[j] by swapping exactly one pair of bits. A "swap exactly one pair of bits" means that nums[i] and nums[j] must have the same number of set bits (population count), and they must differ in exactly two bit positions: one position where nums[i] has a 0 and nums[j] has a 1, and another position where nums[i] has a 1 and nums[j] has a 0.

Input & output

  • Input: nums: number[] - An array of non-negative integers.
  • Output: number - The total count of such pairs (i, j) where i < j.

Clarifications

  • All numbers in nums are non-negative integers.
  • The maximum value of nums[i] will be less than 2^31, meaning we are concerned with bits from position 0 up to 30.
  • A pair (i, j) refers to the indices in the input array. If nums = [1, 2, 1], the pair (0, 1) (values 1 and 2) is distinct from (1, 2) (values 2 and 1). A pair (0, 2) (values 1 and 1) would not be a valid bit-swap anagram pair.

Examples

1

Example 1

Input:

nums = [1, 2, 4]

Output:

3

Note:

Binary representations: 1 = 001_2 2 = 010_2 4 = 100_2

All numbers have a population count of 1.

  • Pair (1, 2): 1 (001) and 2 (010). popcount(1^2) = popcount(011) = 2. Valid.
  • Pair (1, 4): 1 (001) and 4 (100). popcount(1^4) = popcount(101) = 2. Valid.
  • Pair (2, 4): 2 (010) and 4 (100). popcount(2^4) = popcount(110) = 2. Valid. Total valid pairs: 3.
2

Example 2

Input:

nums = [3, 5, 6]

Output:

3

Note:

Binary representations: 3 = 011_2 5 = 101_2 6 = 110_2

All numbers have a population count of 2.

  • Pair (3, 5): 3 (011) and 5 (101). popcount(3^5) = popcount(110) = 2. Valid.
  • Pair (3, 6): 3 (011) and 6 (110). popcount(3^6) = popcount(101) = 2. Valid.
  • Pair (5, 6): 5 (101) and 6 (110). popcount(5^6) = popcount(011) = 2. Valid. Total valid pairs: 3.
3

Example 3

Input:

nums = [1, 2, 3, 4, 5, 6, 7]

Output:

6

Note:

Grouped by population count:

  • popcount = 1: [1, 2, 4] -> These form 3 pairs (as seen in Example 1).
  • popcount = 2: [3, 5, 6] -> These form 3 pairs (as seen in Example 2).
  • popcount = 3: [7] -> No pairs. Total valid pairs: 3 + 3 = 6.
4

Example 4

Input:

nums = [1, 1, 2]

Output:

2

Note:

Binary representations: nums[0] = 1 (001_2) nums[1] = 1 (001_2) nums[2] = 2 (010_2)

All have popcount = 1.

  • Pair (nums[0], nums[1]): 1 and 1. popcount(1^1) = popcount(0) = 0. Not 2. Invalid.
  • Pair (nums[0], nums[2]): 1 and 2. popcount(1^2) = popcount(3) = 2. Valid.
  • Pair (nums[1], nums[2]): 1 and 2. popcount(1^2) = popcount(3) = 2. Valid. Total valid pairs: 2.

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] < 2^31
  • The solution should be efficient enough to pass within typical time limits (~40 minutes).

What interviewers evaluate

  • Correctness of the bitwise logic for identifying 'bit swap anagrams'.
  • Efficiency of the algorithm, avoiding brute-force O(N^2) comparisons.
  • Effective use of appropriate data structures (e.g., hash maps) to optimize lookups.
  • Clarity, readability, and maintainability of the code.

Loading editor...