Bit Manipulation: Frequency Anomalies (The N-Occurrence Model)

Categorizing Frequency Problems

The core problem is identifying numbers that appear $k$ times while all other elements in the array appear $m$ times.

Single Number II (LeetCode 137)

Every element appears three times except for one, which appears exactly once.

Method 1: Per-Bit Counting (Mod 3)

If a digit is present in all numbers except the "special" one $3 \times N$ times, its bitwise sum at any position will be $3N + 1$ (if the special one has that bit) or $3N$ (if it doesn't). Taking the sum modulo 3 perfectly isolates the special number's bit.

public int singleNumber(int[] nums) {
    int ans = 0;
    for (int i = 0; i < 32; i++) {
        int bitSum = 0;
        for (int num : nums) {
            bitSum += (num >> i) & 1;
        }
        // If sum is not divisible by 3, the unique number has bit i set
        if (bitSum % 3 != 0) {
            ans |= (1 << i);
        }
    }
    return ans;
}

Complexity: Time $O(32N) = O(N)$, Space $O(1)$.

Method 2: Digital Circuit State Machine

Use two variables ones and twos to track the count of '1's at each bit position module 3.

• ones: track bits that have appeared $1, 4, 7...$ times (remainder 1).
• twos: track bits that have appeared $2, 5, 8...$ times (remainder 2).

When a third '1' arrives, both ones and twos reset to 0 for that bit.

public int singleNumber(int[] nums) {
    int ones = 0, twos = 0;
    for (int num : nums) {
        // Condition: update ones if num bit is 1, but only if twos is NOT set
        ones = (ones ^ num) & ~twos;
        // Condition: update twos if num bit is 1 and ones is now NOT set
        twos = (twos ^ num) & ~ones;
    }
    return ones;
}

The General $k$ vs $m$ Model

To find a number appearing $k$ times where others appear $m$ times:

public int singleNumberGeneral(int[] nums, int k, int m) {
    int[] bitCounts = new int[32];
    for (int num : nums) {
        for (int i = 0; i < 32; i++) {
            bitCounts[i] += (num >> i) & 1;
        }
    }
    int result = 0;
    for (int i = 0; i < 32; i++) {
        // If (total bit sum at i) mod m equals k mod m
        if (bitCounts[i] % m == k % m) {
            result |= (1 << i);
        }
    }
    return result;
}

Majority Element II (LeetCode 229)

Find all elements that appear more than $\lfloor n/3 \rfloor$ times. (Boyer-Moore extension).

public List<Integer> majorityElement(int[] nums) {
    // There can be at most 2 such elements
    int candidate1 = 0, count1 = 0;
    int candidate2 = 0, count2 = 0;
    
    for (int n : nums) {
        if (n == candidate1) count1++;
        else if (n == candidate2) count2++;
        else if (count1 == 0) { candidate1 = n; count1 = 1; }
        else if (count2 == 0) { candidate2 = n; count2 = 1; }
        else { count1--; count2--; } // Eliminate three distinct elements
    }
    
    // Verification pass
    count1 = count2 = 0;
    for (int n : nums) {
        if (n == candidate1) count1++;
        else if (n == candidate2) count2++;
    }
    
    List<Integer> res = new ArrayList<>();
    if (count1 > nums.length / 3) res.add(candidate1);
    if (count2 > nums.length / 3) res.add(candidate2);
    return res;
}

Lexical Intersection Check (LeetCode 318)

Maximum product of word lengths for words with no common letters.

Bitmasking Strategy: Represent each word as a 26-bit integer (low bit for 'a', high bit for 'z').

public int maxProduct(String[] words) {
    int n = words.length;
    int[] masks = new int[n];
    for (int i = 0; i < n; i++) {
        for (char c : words[i].toCharArray()) {
            masks[i] |= (1 << (c - 'a'));
        }
    }
    
    int maxProd = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // If bitwise AND is zero, words share no common letters
            if ((masks[i] & masks[j]) == 0) {
                maxProd = Math.max(maxProd, words[i].length() * words[j].length());
            }
        }
    }
    return maxProd;
}

Logical Matrix Recap