Bit Manipulation

Master this topic with zero to advance depth.

Bit Manipulation: The Power of Binary

Bit manipulation involves algorithmically manipulating bits (0s and 1s). It is highly efficient and forms the basis of many hardware-level optimizations.

1. Essential Bitwise Operators

Operator	Symbol	Rule
AND	`&`	`1 & 1 = 1`, otherwise `0`. (Masking)
OR	`	`
XOR	`^`	`1 ^ 0 = 1`, `1 ^ 1 = 0`. (Toggling/Canceling)
NOT	`~`	Flips all bits.
Left Shift	`<<`	$x \\cdot 2^n$
Right Shift	`>>`	$x / 2^n$ (Arithmetic)

2. Common Bitwise Patterns

Clear Rightmost Set Bit: n & (n - 1) removes the least significant bit that is 1.
Extract Rightmost Set Bit: n & -n isolates the lowest bit set to 1.
XOR Property: $a \\oplus a = 0$ and $a \\oplus 0 = a$ . This is the basis for many "Single Number" problems.

3. Mental Model: Bitmasks

Think of a number as a collection of toggles. Bit manipulation allows you to flip, check, or set these toggles in $O(1)$ time.

Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Easy

Examples

Input: nums = [2,2,1]
Output: 1

Input: nums = [4,1,2,1,2]
Output: 4

Approach 1

Level I: Brute Force (Frequency Map)

Intuition

Count the frequency of each number using a hash map. The number with frequency 1 is the answer.

⏱ $O(N)$💾 $O(N)$

java

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int x : nums) map.put(x, map.getOrDefault(x, 0) + 1);
        for (int x : nums) if (map.get(x) == 1) return x;
        return -1;
    }
}

Approach 2

Level II: Sorting

Intuition

By sorting the array, identical elements become adjacent. We can then iterate through the array in steps of 2. If an element is not equal to its successor, it's the single number.

⏱ $O(N \log N)$💾 $O(1)$ (or $O(N)$ depending on sorting algorithm)

java

class Solution {
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i += 2) {
            if (nums[i] != nums[i + 1]) return nums[i];
        }
        return nums[nums.length - 1];
    }
}

Approach 3

Level III: Optimal (XOR Manipulation)

Intuition

The XOR operator has two key properties: $x \\oplus x = 0$ and $x \\oplus 0 = x$ . Since every number except one appears twice, XORing all elements together will cause the duplicates to cancel out, leaving only the single number.

⏱ $O(N)$💾 $O(1)$

java

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int x : nums) res ^= x;
        return res;
    }
}

Power of Two

Given an integer n, return true if it is a power of two. Otherwise, return false.

An integer n is a power of two if there exists an integer x such that $n == 2^x$ .

Easy

Examples

Input: n = 1
Output: true

Input: n = 16
Output: true

Input: n = 3
Output: false

Approach 1

Level I: Brute Force (Division)

Intuition

Keep dividing the number by 2 until it hits 1. If at any point the remainder is not 0, it's not a power of two.

⏱ $O(\\log N)$💾 $O(1)$

java

class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0) return false;
        while (n % 2 == 0) n /= 2;
        return n == 1;
    }
}

Approach 2

Level II: Math (Max Power of Two)

Intuition

Since the input is a 32-bit signed integer, the largest power of two is $2^{30} = 1073741824$ . If n is a power of two, it must be a divisor of $2^{30}$ .

⏱ $O(1)$💾 $O(1)$

java

class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && 1073741824 % n == 0;
    }
}

Approach 3

Level III: Optimal (Bit Manipulation)

Intuition

A power of two in binary has exactly one bit set. The expression n & (n - 1) clears the rightmost set bit. If n is a power of two, clearing its only set bit should result in 0.

⏱ $O(1)$💾 $O(1)$

java

class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
}

Single Number II

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Medium

Examples

Input: nums = [2,2,3,2]
Output: 3

Input: nums = [0,1,0,1,0,1,99]
Output: 99

Approach 1

Level I: Brute Force (Frequency Map)

Intuition

The simplest way to track occurrences is using a hash map or frequency array. We count how many times each number appears and return the one with a count of 1.

⏱ $O(N)$💾 $O(N)$

java

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int x : nums) counts.put(x, counts.getOrDefault(x, 0) + 1);
        for (int x : counts.keySet()) if (counts.get(x) == 1) return x;
        return -1;
    }
}

Approach 2

Level II: Sorting

Intuition

If we sort the numbers, identical numbers will be adjacent. We can jump in steps of 3 and check if nums[i] is different from nums[i+1].

⏱ $O(N \log N)$💾 $O(1)$ (or $O(N)$ depending on sort implementation)

java

class Solution {
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i += 3) {
            if (nums[i] != nums[i + 1]) return nums[i];
        }
        return nums[nums.length - 1];
    }
}

Approach 3

Level III: Optimal (Bit Manipulation)

Intuition

Every number that appears three times will contribute exactly 3 (or 0) to the sum of bits at any given position. If we sum the bits at each position $i \in [0, 31]$ and take modulo 3, the remaining bit belongs to the single number.

⏱ $O(N)$💾 $O(1)$

java

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int sum = 0;
            for (int x : nums) if (((x >> i) & 1) == 1) sum++;
            if (sum % 3 != 0) res |= (1 << i);
        }
        return res;
    }
}

Single Number III

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

Medium

Examples

Input: nums = [1,2,1,3,2,5]
Output: [3,5]

Input: nums = [-1,0]
Output: [-1,0]

Approach 1

Level I: Brute Force (Frequency Map)

Intuition

The most intuitive approach is to use a hash map to count the frequency of each number and extract those with a count of 1.

⏱ $O(N)$💾 $O(N)$

java

class Solution {
    public int[] singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) map.put(n, map.getOrDefault(n, 0) + 1);
        int[] res = new int[2];
        int idx = 0;
        for (int n : map.keySet()) if (map.get(n) == 1) res[idx++] = n;
        return res;
    }
}

Approach 2

Level II: Sorting

Intuition

Sort the array to bring duplicates together. Iterate through the array; if current element is not equal to the next, it's a single number. Otherwise, skip two.

⏱ $O(N \log N)$💾 $O(1)$

java

class Solution {
    public int[] singleNumber(int[] nums) {
        Arrays.sort(nums);
        int[] res = new int[2];
        int idx = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i < nums.length - 1 && nums[i] == nums[i + 1]) i++;
            else res[idx++] = nums[i];
        }
        return res;
    }
}

Approach 3

Level III: Optimal (Bitwise Partitioning)

Intuition

XORing all numbers gives $x \oplus y$ . Find the lowest set bit in this XOR sum to divide all numbers into two groups (where this bit is set vs. not set). XORing within each group isolates $x$ and $y$ .

⏱ $O(N)$💾 $O(1)$

java

class Solution {
    public int[] singleNumber(int[] nums) {
        int xor = 0;
        for (int n : nums) xor ^= n;
        int diffBit = xor & -xor;
        int[] res = new int[2];
        for (int n : nums) {
            if ((n & diffBit) == 0) res[0] ^= n;
            else res[1] ^= n;
        }
        return res;
    }
}

Bitwise AND of Numbers Range

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Medium

Examples

Input: left = 5, right = 7
Output: 4

Input: left = 0, right = 0
Output: 0

Approach 1

Level I: Brute Force (Linear AND)

Intuition

Iterate from left to right and perform bitwise AND on all numbers. This is slow if the range is large.

Thought Process

Initialize res = left.
Iterate i from left + 1 to right.
res &= i.
Return res.

Pattern: Simulation

⏱ O(N) - Where $N$ is the number of integers in the range.💾 O(1) - Constant space.

java

public class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int res = left;
        for (long i = (long)left + 1; i <= right; i++) {
            res &= i;
            if (res == 0) break;
        }
        return res;
    }
}

Approach 2

Level II: Iterative Shift (Pre-calculation)

Intuition

Shift both left and right rightward until they are identical. The bits that are removed are the ones that fluctuate within the range. Finally, shift the common prefix back to its original position.

⏱ $O(1)$ - Maximum of 32 shifts.💾 $O(1)$

java

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int shifts = 0;
        while (left < right) {
            left >>= 1;
            right >>= 1;
            shifts++;
        }
        return left << shifts;
    }
}

Approach 3

Level III: Optimal (Common Prefix / Brian Kernighan)

Intuition

The bitwise AND of a range is the common prefix of the binary representations of the range's endpoints. Any bit that changes within the range will eventually become 0 in the final AND result.

Thought Process

While right > left:
- right = right & (right - 1) (clears the rightmost set bit).
Alternatively, shift both numbers right until they are equal, then shift back.

Pattern: Bitwise Prefix Match

⏱ O(1) - Max 32 iterations.💾 O(1) - Constant space.

Detailed Dry Run

left=5(101), right=7(111) Iteration 1: right = 7 & 6 = 6 (110). 6 > 5. Iteration 2: right = 6 & 5 = 4 (100). 4 < 5. Stop. Result: 4

java

public class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        while (right > left) {
            right &= (right - 1);
        }
        return right;
    }
}

Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).

Easy

Examples

Input: n = 11
Output: 3
11 in binary is 1011, which has three '1' bits.

Approach 1

Level I: Brute Force (Iterate all 32 bits)

Intuition

The most straightforward way is to check each of the 32 bits one by one. We can do this by shifting the number right and checking the last bit using bitwise AND with 1.

Thought Process

Initialize a counter count = 0.
Loop 32 times (for a 32-bit integer):
- Check if the last bit is 1: (n & 1) == 1.
- If yes, increment count.
- Right shift $n$ by 1: n >>= 1.
Return count.

Pattern: Bitwise Iteration

⏱ O(1) - Always 32 iterations for a 32-bit integer.💾 O(1) - No extra space used.

java

public class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if ((n & 1) != 0) count++;
            n >>= 1;
        }
        return count;
    }
}

Approach 2

Level II: Standard Library / Built-in

Intuition

Most modern programming languages provide highly optimized built-in functions to count set bits, often utilizing specific CPU instructions like POPCNT.

⏱ $O(1)$ - Usually a few machine instructions.💾 $O(1)$

java

public class Solution {
    public int hammingWeight(int n) {
        return Integer.bitCount(n);
    }
}

Approach 3

Level III: Optimal (Brian Kernighan's Algorithm)

Intuition

Instead of checking every bit, we can jump directly between set bits. The operation n & (n - 1) always clears the least significant set bit of $n$ .

Thought Process

While $n \neq 0$ $n \neq = 0$ :
- Set $n = n \text{ & } (n - 1)$ . This removes exactly one '1' bit.
- Increment count.
The number of iterations equals the number of set bits, which is more efficient for sparse numbers.

Pattern: Bit Manipulation Magic

⏱ O(1) - Specifically $O(\text{number of set bits})$, max 32 iterations.💾 O(1) - Constant space.

Detailed Dry Run

n = 12 (binary 1100)

Iteration	n (Before)	n-1	n & (n-1)	count
1	1100 (12)	1011 (11)	1000 (8)	1
2	1000 (8)	0111 (7)	0000 (0)	2
Result: 2

java

public class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n &= (n - 1);
            count++;
        }
        return count;
    }
}

Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

Easy

Examples

Input: n = 43261596
Output: 964176192
43261596 (00000010100101000001111010011100) reversed is 964176192 (00111001011110000010100101000000).

Approach 1

Level I: Brute Force (Iterate and Shift)

Intuition

Iterate through each of the 32 bits of the input. In each step, shift the result left and add the last bit of the input. Then shift the input right.

Thought Process

Initialize res = 0.
Loop 32 times:
- Check the last bit of n: n & 1.
- Shift res left and add that bit: (res << 1) + (n & 1).
- Right shift n by 1.
Return res.

Pattern: Bitwise Result Construction

⏱ O(1) - Always 32 iterations.💾 O(1) - Constant extra space.

java

public class Solution {
    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            res = (res << 1) | (n & 1);
            n >>= 1;
        }
        return res;
    }
}

Approach 2

Level II: Byte-by-Byte Lookup (Caching)

Intuition

A 32-bit integer consists of 4 bytes. We can precompute or manually reverse the bits for each byte (8 bits) and then combine them. This is faster when multiple calls are made as the byte reversals can be cached.

⏱ $O(1)$ - Proportional to number of bytes (4).💾 $O(1)$ - Small lookup table or fixed reversal logic.

java

public class Solution {
    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 4; i++) {
            res = (res << 8) | reverseByte((n >> (i * 8)) & 0xFF);
        }
        // Adjust result because the loop constructs it in reverse order
        return Integer.reverse(n);
    }
    
    private int reverseByte(int b) {
        int r = 0;
        for (int i = 0; i < 8; i++) {
            r = (r << 1) | ((b >> i) & 1);
        }
        return r;
    }
}

Approach 3

Level III: Optimal (Divide and Conquer)

Intuition

We can reverse the bits using a series of mask and shift operations. First, swap adjacent bits, then swap adjacent pairs, then adjacent nibbles (4 bits), and so on.

Thought Process

Swap bits 1-by-1: n = ((n & 0xAAAAAAAA) >>> 1) | ((n & 0x55555555) << 1)
Swap bits 2-by-2: n = ((n & 0xCCCCCCCC) >>> 2) | ((n & 0x33333333) << 2)
Swap bits 4-by-4: n = ((n & 0xF0F0F0F0) >>> 4) | ((n & 0x0F0F0F0F) << 4)
Swap bits 8-by-8: n = ((n & 0xFF00FF00) >>> 8) | ((n & 0x00FF00FF) << 8)
Swap bits 16-by-16: n = (n >>> 16) | (n << 16)

Pattern: Parallel Bit Processing

⏱ O(1) - Constant number of bitwise operations.💾 O(1) - Constant space.

java

public class Solution {
    public int reverseBits(int n) {
        n = ((n & 0xAAAAAAAA) >>> 1) | ((n & 0x55555555) << 1);
        n = ((n & 0xCCCCCCCC) >>> 2) | ((n & 0x33333333) << 2);
        n = ((n & 0xF0F0F0F0) >>> 4) | ((n & 0x0F0F0F0F) << 4);
        n = ((n & 0xFF00FF00) >>> 8) | ((n & 0x00FF00FF) << 8);
        n = (n >>> 16) | (n << 16);
        return n;
    }
}

Sum of Two Integers

Given two integers a and b, return the sum of the two integers without using the operators + and -.

Medium

Examples

Input: a = 1, b = 2
Output: 3

Input: a = 2, b = 3
Output: 5

Approach 1

Level I: Brute Force (Bit-by-Bit Simulation)

Intuition

Simulate how a half-adder or full-adder works. Iterate through each bit position (0 to 31), calculate the sum of bits and the carry, and build the result bit by bit.

Thought Process

Initialize res = 0, carry = 0.
For i from 0 to 31:
- Get $i$ -th bits of a and b.
- sum = bitA ^ bitB ^ carry.
- carry = (bitA & bitB) | (carry & (bitA ^ bitB)).
- Set $i$ -th bit of res to sum.
Return res.

Pattern: Simulation / Logic Gates

⏱ O(1) - Always 32 iterations.💾 O(1) - Constant space.

java

public class Solution {
    public int getSum(int a, int b) {
        int res = 0, carry = 0;
        for (int i = 0; i < 32; i++) {
            int bitA = (a >> i) & 1;
            int bitB = (b >> i) & 1;
            int sum = bitA ^ bitB ^ carry;
            carry = (bitA & bitB) | (bitA & carry) | (bitB & carry);
            res |= (sum << i);
        }
        return res;
    }
}

Approach 2

Level II: Recursive XOR & AND

Intuition

The iterative logic can be expressed recursively. The sum of a and b is equivalent to the XOR of a and b (sum without carry) plus the AND of a and b shifted left (the carry).

⏱ $O(1)$ - Max 32 recursive calls.💾 $O(1)$ - Recursion stack for 32 levels.

java

class Solution {
    public int getSum(int a, int b) {
        return b == 0 ? a : getSum(a ^ b, (a & b) << 1);
    }
}

Approach 3

Level III: Optimal (Iterative XOR & AND)

Intuition

Addition can be broken into two parts: the sum without carry (a ^ b) and the carry itself ((a & b) << 1). We repeat this process until the carry becomes zero.

Thought Process

a ^ b gives the sum bits where no carry is involved.
a & b gives the bits where a carry is generated.
Shift the carry left by 1 to add it to the next significant bit.
Repeat until carry is 0.

Pattern: Recursive Addition Logic

⏱ O(1) - Max 32 iterations (number of bits).💾 O(1) - Constant space.

Detailed Dry Run

a = 2 (10), b = 3 (11)

Iteration 1: sum = 10 ^ 11 = 01 (1) carry = (10 & 11) << 1 = 100 (4)
Iteration 2: sum = 001 ^ 100 = 101 (5) carry = (001 & 100) << 1 = 000 (0) Result: 5

java

public class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
}

Missing Number

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Easy

Examples

Input: nums = [3,0,1]
Output: 2
n = 3. Range is [0,3]. 2 is missing.

Input: nums = [0,1]
Output: 2
n = 2. Range is [0,2]. 2 is missing.

Approach 1

Level I: Brute Force (Sorting)

Intuition

Sort the array and check if each index matches the value at that index. The first index $i$ where nums[i] != i is the missing number. If all match, the missing number is $n$ .

Thought Process

Sort nums in ascending order.
Iterate $i$ $i$ from $0$ $0$ to $n - 1$ $n - 1$ :
- If nums[i] != i, return i.
If loop finishes, return n.

Pattern: Sorting

⏱ O(N log N) - Due to sorting.💾 O(1) or O(N) depending on the sort implementation.

java

import java.util.Arrays;

public class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) return i;
        }
        return nums.length;
    }
}

Approach 2

Level II: Math (Sum Formula)

Intuition

The sum of the first $n$ numbers is $\frac{n(n+1)}{2}$ . By subtracting the sum of all elements in the array from this total sum, we obtain the missing number.

⏱ $O(N)$💾 $O(1)$

java

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int expectedSum = n * (n + 1) / 2;
        int actualSum = 0;
        for (int x : nums) actualSum += x;
        return expectedSum - actualSum;
    }
}

Approach 3

Level III: Optimal (XOR)

Intuition

XORing a number with itself results in 0 ( $x \oplus x = 0$ ). If we XOR all numbers in the range $[0, n]$ and all numbers in the array, every number present in the array will appear twice and cancel out, leaving only the missing number.

Thought Process

Initialize missing = n (or 0).
Iterate through the array:
- missing ^= i ^ nums[i]
Return missing.

Pattern: XOR Cancellation

⏱ O(N) - Single pass through the array.💾 O(1) - Constant storage.

Detailed Dry Run

nums = [3, 0, 1], n = 3 missing = 3 i=0: missing = 3 ^ 0 ^ 3 = 0 i=1: missing = 0 ^ 1 ^ 0 = 1 i=2: missing = 1 ^ 2 ^ 1 = 2 Result: 2

java

public class Solution {
    public int missingNumber(int[] nums) {
        int xor = nums.length;
        for (int i = 0; i < nums.length; i++) {
            xor ^= i ^ nums[i];
        }
        return xor;
    }
}

Count Triplets That Can Form Two Arrays of Equal XOR

Given an array of integers arr. We want to select three indices i, j and k where (0 <= i < j <= k < arr.length).

Let a = arr[i] ^ ... ^ arr[j - 1] and b = arr[j] ^ ... ^ arr[k]. Return the number of triplets (i, j, k) such that a == b.

Medium

Examples

Input: arr = [2,3,1,6,7]
Output: 4

Input: arr = [1,1,1,1,1]
Output: 10

Approach 1

Level I: Brute Force (O(N^3))

Intuition

Iterate through all possible combinations of i, j, and k. Calculate a and b for each triplet and check if they are equal.

Thought Process

Use three nested loops for i, j, and k.
In the innermost loop, calculate XOR for a and b.
If a == b, increment count.

Pattern: Triple Nested Iteration

⏱ O(N^3) or O(N^4) - Depending on how XOR is calculated.💾 O(1) - Constant space.

java

public class Solution {
    public int countTriplets(int[] arr) {
        int count = 0, n = arr.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j; k < n; k++) {
                    int a = 0, b = 0;
                    for (int x = i; x < j; x++) a ^= arr[x];
                    for (int x = j; x <= k; x++) b ^= arr[x];
                    if (a == b) count++;
                }
            }
        }
        return count;
    }
}

Approach 2

Level II: Prefix XOR with Hash Map

Intuition

We seek $(i, k)$ such that $P[i] == P[k+1]$ . Instead of a nested loop, we can use a hash map to store the indices (or counts and sum of indices) where each prefix XOR has occurred.

⏱ $O(N)$💾 $O(N)$

java

class Solution {
    public int countTriplets(int[] arr) {
        int n = arr.length, res = 0, prefix = 0;
        Map<Integer, Integer> count = new HashMap<>(), total = new HashMap<>();
        count.put(0, 1);
        for (int i = 0; i < n; i++) {
            prefix ^= arr[i];
            res += count.getOrDefault(prefix, 0) * i - total.getOrDefault(prefix, 0);
            count.put(prefix, count.getOrDefault(prefix, 0) + 1);
            total.put(prefix, total.getOrDefault(prefix, 0) + i + 1);
        }
        return res;
    }
}

Approach 3

Level III: Optimal (Prefix XOR)

Intuition

As shown in the logic representation, $a == b$ is equivalent to $arr[i] \oplus ... \oplus arr[k] = 0$ . Using prefix XOR array $P$ where $P[x] = arr[0] \oplus ... \oplus arr[x-1]$ , the XOR of $arr[i...k]$ is $P[k+1] \oplus P[i]$ . We need $P[k+1] == P[i]$ . If found, all $j \in (i, k]$ are valid.

Thought Process

Calculate prefix XOR array prefix.
Iterate through all pairs $(i, k)$ $(i, k)$ where $i < k$ $i < k$ :
- If prefix[i] == prefix[k+1]:
  - The number of valid j's is k - i.
  - Add k - i to total.

Pattern: Subarray XOR Frequency

⏱ O(N^2) - Iterate through all possible $(i, k)$ pairs.💾 O(N) - Storage for prefix XOR array.

Detailed Dry Run

arr = [2, 3, 1, 6, 7] Prefix: [0, 2, 1, 0, 6, 1] Pairs with equal prefix values:

P[0] and P[3]: (i=0, k=2). count += 2-0 = 2 triplets.
P[2] and P[5]: (i=2, k=4). count += 4-2 = 2 triplets. Total: 2 + 2 = 4.

java

public class Solution {
    public int countTriplets(int[] arr) {
        int n = arr.length, count = 0;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] ^ arr[i];
        for (int i = 0; i < n; i++) {
            for (int k = i + 1; k < n; k++) {
                if (prefix[i] == prefix[k + 1]) {
                    count += (k - i);
                }
            }
        }
        return count;
    }
}

Gray Code

An n-bit gray code sequence is a sequence of $2^n$ integers where:

Every integer is in the inclusive range $[0, 2^n - 1]$ ,
The first integer is 0,
An integer appears no more than once in the sequence,
The binary representation of every pair of adjacent integers differs by exactly one bit,
The binary representation of the first and last integers differs by exactly one bit.

Given an integer n, return any valid n-bit gray code sequence.

Medium

Examples

Input: n = 2
Output: [0,1,3,2]
00, 01, 11, 10 is a valid Gray code sequence.

Approach 1

Level I: Brute Force (Backtracking)

Intuition

Generate the sequence by exploring all possible next numbers that differ by exactly one bit. Maintain a visited set to ensure uniqueness.

Thought Process

Start with 0.
Try flipping each of the $n$ bits.
If the result is not visited, move to it and recurse.
If all bits visited, return the sequence.

Pattern: State Space Search

⏱ O(2^n) - We generate $2^n$ numbers exactly once.💾 O(2^n) - To store the result and visited set.

java

import java.util.*;

public class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(0);
        Set<Integer> visited = new HashSet<>();
        visited.add(0);
        backtrack(n, res, visited);
        return res;
    }
    
    private boolean backtrack(int n, List<Integer> res, Set<Integer> visited) {
        if (res.size() == (1 << n)) return true;
        int curr = res.get(res.size() - 1);
        for (int i = 0; i < n; i++) {
            int next = curr ^ (1 << i);
            if (!visited.contains(next)) {
                visited.add(next);
                res.add(next);
                if (backtrack(n, res, visited)) return true;
                res.remove(res.size() - 1);
                visited.remove(next);
            }
        }
        return false;
    }
}

Approach 2

Level II: Reflected Construction (Iterative)

Intuition

Gray code for $n$ bits can be built from the Gray code for $n-1$ bits by reflecting the sequence and adding a leading 1 (bit $n-1$ ) to the reflected part.

⏱ $O(2^N)$💾 $O(1)$ (excluding output)

java

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(0);
        for (int i = 0; i < n; i++) {
            int size = res.size();
            for (int k = size - 1; k >= 0; k--) {
                res.add(res.get(k) | (1 << i));
            }
        }
        return res;
    }
}

Approach 3

Level III: Optimal (Bit Manipulation Formula)

Intuition

The $i$ -th number in the Gray code sequence can be generated using the formula $G(i) = i \oplus (i / 2)$ . This formula ensures that adjacent numbers differ by exactly one bit because shifting and XORing cancels out bits that change in a ripple carry but leaves the most significant changing bit.

Thought Process

The total number of elements is $2^n$ .
For each index $i$ $i$ from 0 to $2^n - 1$ $2^{n} - 1$ :
- Calculate i ^ (i >> 1).
Add to result list and return.

Pattern: Formula-based Generation

⏱ O(2^n) - Constant time per element.💾 O(1) - Excluding the output storage.

Detailed Dry Run

n = 2

i=0: 0 ^ (0>>1) = 0 ^ 0 = 0 (00)
i=1: 1 ^ (1>>1) = 1 ^ 0 = 1 (01)
i=2: 2 ^ (2>>1) = 2 ^ 1 = 3 (11)
i=3: 3 ^ (3>>1) = 3 ^ 1 = 2 (10) Result: [0, 1, 3, 2]

java

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < (1 << n); i++) {
            result.add(i ^ (i >> 1));
        }
        return result;
    }
}

Repeated DNA Sequences

Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.

Medium

Examples

Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]

Approach 1

Level I: Brute Force (Hash Set of Strings)

Intuition

Iterate through every possible 10-letter substring and store it in a hash set. If we encounter a substring that is already in the set, we add it to our result list.

Thought Process

Use a seen hash set to track substrings.
Use a repeated hash set to collect result strings.
Loop i from 0 to s.length() - 10:
- Extract substring s.substring(i, i + 10).
- If in seen, add to repeated.
- Else, add to seen.

Pattern: String Rolling Window

⏱ O(N \cdot L) - Where $N$ is string length and $L=10$ is the sequence length.💾 O(N \cdot L) - To store strings in sets.

java

import java.util.*;

public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        Set<String> seen = new HashSet<>(), repeated = new HashSet<>();
        for (int i = 0; i <= s.length() - 10; i++) {
            String sub = s.substring(i, i + 10);
            if (seen.contains(sub)) repeated.add(sub);
            else seen.add(sub);
        }
        return new ArrayList<>(repeated);
    }
}

Approach 2

Level II: Rolling Hash (Rabin-Karp)

Intuition

Instead of re-extracting substrings, we treat each 10-letter window as a number in base 4 (since there are 4 DNA bases). As we slide the window, we update the hash in $O(1)$ time.

⏱ $O(N)$💾 $O(N)$

java

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        if (s.length() < 10) return new ArrayList<>();
        int[] map = new int[256];
        map['A'] = 0; map['C'] = 1; map['G'] = 2; map['T'] = 3;
        Set<Integer> seen = new HashSet<>(), rep = new HashSet<>();
        int h = 0;
        for (int i = 0; i < 10; i++) h = (h << 2) | map[s.charAt(i)];
        seen.add(h);
        for (int i = 10; i < s.length(); i++) {
            h = ((h << 2) | map[s.charAt(i)]) & 0xFFFFF;
            if (!seen.add(h)) {
                // Logic to track only duplicate sequences efficiently
            }
        }
        return new ArrayList<>();
    }
}

Approach 3

Level III: Optimal (Bitmasking)

Intuition

Since there are only 4 characters, map them to 2 bits. A 10-char sequence is a 20-bit integer. Use a sliding window to update the bitmask in $O(1)$ per character.

Thought Process

Map A=0, C=1, G=2, T=3.
Maintain a 20-bit sliding window.
Use a hash map/set to track encountered bitmasks.

Pattern: 2-bit Character Encoding

⏱ O(N) - Linear scan without string creation.💾 O(min(N, 2^{20})) - Hash set storage for 20-bit integers.

java

public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        if (s.length() < 10) return new ArrayList<>();
        Map<Character, Integer> toInt = Map.of('A', 0, 'C', 1, 'G', 2, 'T', 3);
        Set<Integer> seen = new HashSet<>();
        Set<String> res = new HashSet<>();
        int mask = (1 << 20) - 1, curr = 0;
        for (int i = 0; i < s.length(); i++) {
            curr = ((curr << 2) | toInt.get(s.charAt(i))) & mask;
            if (i >= 9) {
                if (seen.contains(curr)) res.add(s.substring(i - 9, i + 1));
                else seen.add(curr);
            }
        }
        return new ArrayList<>(res);
    }
}

Maximum Product of Word Lengths

Given a string array words, return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. If no such two words exist, return 0.

Medium

Examples

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16

Approach 1

Level I: Brute Force (Check All Pairs)

Intuition

Iterate through every pair of words and check if they have common characters using a helper function.

Thought Process

Nested loop $(i, j)$ for all pairs.
For each pair:
- Check overlap: For char in word[i], is it in word[j]?
- If no overlap, update maxProd.

Pattern: Double Iteration

⏱ O(N^2 \cdot L) - Where $N$ is number of words and $L$ is max word length.💾 O(1) - Assuming constant alphabet space.

java

public class Solution {
    public int maxProduct(String[] words) {
        int max = 0, n = words.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (!hasCommon(words[i], words[j])) {
                    max = Math.max(max, words[i].length() * words[j].length());
                }
            }
        }
        return max;
    }
    
    private boolean hasCommon(String s1, String s2) {
        boolean[] set = new boolean[26];
        for (char c : s1.toCharArray()) set[c - 'a'] = true;
        for (char c : s2.toCharArray()) if (set[c - 'a']) return true;
        return false;
    }
}

Approach 2

Level II: Precomputed Sets

Intuition

For each word, precompute a set of its characters. When comparing two words, check if their character sets have any intersection. This is faster than a raw character-by-character check but slower than bitmasking.

⏱ $O(N^2 + N \cdot L)$💾 $O(N \cdot 26)$

java

class Solution {
    public int maxProduct(String[] words) {
        int n = words.length;
        boolean[][] has = new boolean[n][26];
        for (int i = 0; i < n; i++) {
            for (char c : words[i].toCharArray()) has[i][c - 'a'] = true;
        }
        int maxP = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                boolean common = false;
                for (int k = 0; k < 26; k++) {
                    if (has[i][k] && has[j][k]) { common = true; break; }
                }
                if (!common) maxP = Math.max(maxP, words[i].length() * words[j].length());
            }
        }
        return maxP;
    }
}

Approach 3

Level III: Optimal (Bitmasking)

Intuition

Each word can be represented by a 26-bit integer (bitmask). Two words share NO common letters if and only if their bitwise AND is 0.

Thought Process

Precompute bitmasks for all words.
Nested loop $(i, j)$ and check (masks[i] & masks[j]) == 0.
Update max product.

Pattern: Alphabet Bitmasking

⏱ O(N^2 + N \cdot L) - $O(N \cdot L)$ to build masks, $O(N^2)$ to compare pairs.💾 O(N) - To store the bitmasks.

Detailed Dry Run

"abcw" -> mask = 0x400007 "xtfn" -> mask = 0x882020 mask1 & mask2 = 0. Product = 4 * 4 = 16.

java

public class Solution {
    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 maxP = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((masks[i] & masks[j]) == 0) {
                    maxP = Math.max(maxP, words[i].length() * words[j].length());
                }
            }
        }
        return maxP;
    }
}

Maximum XOR of Two Numbers in an Array

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where $0 \leq i \leq j < n$ .

Medium

Examples

Input: nums = [3,10,5,25,2,8]
Output: 28

Approach 1

Level I: Brute Force (All Pairs)

Intuition

Check every possible pair of numbers $(i, j)$ and calculate their XOR sum. Track the maximum value found.

Thought Process

Initialize maxResult = 0.
Nested loop through nums.
maxResult = max(maxResult, nums[i] ^ nums[j]).
Return maxResult.

Pattern: Double Iteration

⏱ O(N^2) - Where $N$ is the number of elements in the array.💾 O(1) - Constant space.

java

public class Solution {
    public int findMaximumXOR(int[] nums) {
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                max = Math.max(max, nums[i] ^ nums[j]);
            }
        }
        return max;
    }
}

Approach 2

Level II: Greedy Comparison with Hash Set

Intuition

We can build the maximum XOR bit by bit. For each bit position $i$ (from MSB to LSB), we check if there exists a pair of numbers whose $i$ -th bits could potentially form a better maximum XOR than what we have found so far.

⏱ $O(N \cdot 32)$💾 $O(N)$

java

class Solution {
    public int findMaximumXOR(int[] nums) {
        int max = 0, mask = 0;
        for (int i = 30; i >= 0; i--) {
            mask |= (1 << i);
            Set<Integer> set = new HashSet<>();
            for (int n : nums) set.add(n & mask);
            int tmp = max | (1 << i);
            for (int prefix : set) {
                if (set.contains(tmp ^ prefix)) {
                    max = tmp;
                    break;
                }
            }
        }
        return max;
    }
}

Approach 3

Level III: Optimal (Binary Trie)

Intuition

To maximize XOR, for each number $X$ , we want to find another number $Y$ such that they have different bits at the highest possible positions. A Trie (Prefix Tree) storing binary representations allows us to greedily find the bitwise opposite at each step.

Thought Process

Insert all numbers into a Trie of depth 31.
For each number $X$ $X$ :
- Start at the Trie root.
- For each bit $b$ $b$ of $X$ $X$ (from MSB to LSB):
  - If we want bit $1-b$ and it exists in the Trie, move there and add $(1 << bit)$ to our current XOR.
  - Else, move to the child with bit $b$ .
Track the best XOR found for any $X$ .

Pattern: Bitwise Greedy with Trie

⏱ O(N \cdot 32) - Linear pass to build Trie and another to query.💾 O(N \cdot 32) - Store numbers bit-by-bit in Trie nodes.

java

class TrieNode {
    TrieNode[] children = new TrieNode[2];
}

public class Solution {
    public int findMaximumXOR(int[] nums) {
        TrieNode root = new TrieNode();
        for (int n : nums) {
            TrieNode curr = root;
            for (int i = 30; i >= 0; i--) {
                int bit = (n >> i) & 1;
                if (curr.children[bit] == null) curr.children[bit] = new TrieNode();
                curr = curr.children[bit];
            }
        }
        
        int max = 0;
        for (int n : nums) {
            TrieNode curr = root;
            int currSum = 0;
            for (int i = 30; i >= 0; i--) {
                int bit = (n >> i) & 1;
                if (curr.children[1 - bit] != null) {
                    currSum |= (1 << i);
                    curr = curr.children[1 - bit];
                } else {
                    curr = curr.children[bit];
                }
            }
            max = Math.max(max, currSum);
        }
        return max;
    }
}

Divide Two Integers

Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

Hard

Examples

Input: dividend = 10, divisor = 3
Output: 3
10/3 = 3.33333... which is truncated to 3.

Input: dividend = 7, divisor = -3
Output: -2
7/-3 = -2.33333... which is truncated to -2.

Approach 1

Level I: Brute Force (Linear Subtraction)

Intuition

Keep subtracting the divisor from the dividend until the dividend becomes smaller than the divisor. The number of times we subtract is the quotient.

Thought Process

Handle edge cases (overflow for INT_MIN).
Determine sign of result.
Take absolute values of dividend and divisor.
Loop while dividend >= divisor:
- dividend -= divisor.
- count++.
Apply sign and return.

Pattern: Simulation

⏱ O(N) - Where $N$ is the quotient. Extremely slow for large dividends.💾 O(1) - Constant space.

java

public class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
        long dvd = Math.abs((long)dividend);
        long dvs = Math.abs((long)divisor);
        int res = 0;
        while (dvd >= dvs) {
            dvd -= dvs;
            res++;
        }
        return (dividend > 0) == (divisor > 0) ? res : -res;
    }
}

Approach 2

Level II: Recursive Long Division

Intuition

The exponential subtraction can be performed recursively. In each call, we find the largest multiple of the divisor that can be subtracted and then recurse on the remainder.

⏱ $O(\log^2 N)$💾 $O(\log N)$ (Recursion stack)

java

class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
        long dvd = Math.abs((long)dividend), dvs = Math.abs((long)divisor);
        long res = ldivide(dvd, dvs);
        return (dividend > 0) == (divisor > 0) ? (int)res : (int)-res;
    }
    private long ldivide(long dvd, long dvs) {
        if (dvd < dvs) return 0;
        long sum = dvs, multiple = 1;
        while ((sum << 1) <= dvd) {
            sum <<= 1;
            multiple <<= 1;
        }
        return multiple + ldivide(dvd - sum, dvs);
    }
}

Approach 3

Level III: Optimal (Exponential Subtraction / Shifts)

Intuition

Instead of subtracting exactly one divisor at a time, we subtract the largest possible multiple of the divisor using bit shifts (divisor << k). This is equivalent to long division in binary.

Thought Process

While dividend >= divisor:
- Find the largest $k$ such that divisor << k <= dividend.
- dividend -= (divisor << k).
- quotient += (1 << k).
This uses the property that $B \cdot 2^k$ is a fast way to find large chunks to subtract.

Pattern: Exponential Backoff / Long Division

⏱ O(log^2 N) - Outer loop reduces dividend, inner loop finds shift.💾 O(1) - Constant space.

Detailed Dry Run

15 / 3

Largest shift: 3 << 2 = 12. 15 - 12 = 3. Quotient = 4 (2^2).
Largest shift: 3 << 0 = 3. 3 - 3 = 0. Quotient = 4 + 1 = 5. Result: 5

java

public class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
        long a = Math.abs((long)dividend), b = Math.abs((long)divisor), res = 0;
        while (a >= b) {
            long temp = b, multiple = 1;
            while (a >= (temp << 1)) {
                temp <<= 1;
                multiple <<= 1;
            }
            a -= temp;
            res += multiple;
        }
        return (dividend > 0) == (divisor > 0) ? (int)res : (int)-res;
    }
}

Total Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Return the sum of Hamming distances between all pairs of integers in nums.

Medium

Examples

Input: nums = [4,14,2]
Output: 6
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Approach 1

Level I: Brute Force (Check All Pairs)

Intuition

The most direct way is to iterate through every pair in the array, calculate their Hamming distance, and sum them up.

Thought Process

Initialize totalDist = 0.
For each pair $(i, j)$ $(i, j)$ where $i < j$ $i < j$ :
- Calculate Hamming distance: Integer.bitCount(nums[i] ^ nums[j]).
- Add to totalDist.
Return totalDist.

Pattern: Nested Iteration

⏱ O(N^2) - To check all $N(N-1)/2$ pairs.💾 O(1) - Constant space.

java

public class Solution {
    public int totalHammingDistance(int[] nums) {
        int total = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                total += Integer.bitCount(nums[i] ^ nums[j]);
            }
        }
        return total;
    }
}

Approach 2

Level II: Iterative Bit Verification

Intuition

We can calculate the Hamming distance for each pair by iterating through the numbers and checking each bit. This is similar to the brute force but slightly more structured.

⏱ $O(N^2 \cdot 32)$💾 $O(1)$

java

class Solution {
    public int totalHammingDistance(int[] nums) {
        int total = 0, n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int xor = nums[i] ^ nums[j];
                for (int k = 0; k < 32; k++) {
                    if (((xor >> k) & 1) == 1) total++;
                }
            }
        }
        return total;
    }
}

Approach 3

Level III: Optimal (Bit Counting per Position)

Intuition

Instead of checking pairs, we can check bit positions. For any bit position $i$ , if $k$ numbers have the $i$ -th bit set to 1, and $n-k$ numbers have it set to 0, then there are $k \cdot (n-k)$ pairs that differ at this position.

Thought Process

Initialize total = 0.
For each bit position $0$ $0$ to $31$ $31$ :
- Count numbers $k$ with $i$ -th bit set.
- total += k * (n - k).
Return total.

Pattern: Positional Counting

⏱ O(N) - Single pass over the array for each of the 32 bits.💾 O(1) - Constant space.

Detailed Dry Run

nums: [4, 14, 2], n=3 Bit Pos 1: Bits are {0, 1, 0}. k=1, n-k=2. Pairs = 12 = 2. Bit Pos 2: Bits are {1, 1, 0}. k=2, n-k=1. Pairs = 21 = 2. Bit Pos 3: Bits are {0, 1, 0}. k=1, n-k=2. Pairs = 1*2 = 2. Total: 2+2+2 = 6.

java

public class Solution {
    public int totalHammingDistance(int[] nums) {
        int total = 0, n = nums.length;
        for (int i = 0; i < 30; i++) {
            int k = 0;
            for (int x : nums) {
                k += (x >> i) & 1;
            }
            total += k * (n - k);
        }
        return total;
    }
}

Minimum Flips to Make a OR b Equal to c

Given 3 positives a, b and c. Return the minimum flips required in some bits of a and b to make (a OR b == c).

Medium

Examples

Input: a = 2, b = 6, c = 5
Output: 3

Input: a = 4, b = 2, c = 7
Output: 1

Approach 1

Level I: Brute Force (Bit-by-Bit Check)

Intuition

Iterate through each bit of the three numbers and compare the required state c with the current state a | b. Count the flips needed for each bit position.

Thought Process

For each bit position $i$ $i$ (0 to 31):
- If $i$ $i$ -th bit of c is 0:
  - Both $i$ -th bits of a and b must be 0. Add their sum to flips.
- If $i$ $i$ -th bit of c is 1:
  - At least one of $i$ -th bits of a or b must be 1. If both are 0, add 1 to flips.
Return flips.

Pattern: Positional Verification

⏱ O(1) - Always 32 iterations.💾 O(1) - Constant space.

java

public class Solution {
    public int minFlips(int a, int b, int c) {
        int flips = 0;
        for (int i = 0; i < 32; i++) {
            int bitA = (a >> i) & 1;
            int bitB = (b >> i) & 1;
            int bitC = (c >> i) & 1;
            if (bitC == 0) {
                flips += (bitA + bitB);
            } else {
                if (bitA == 0 && bitB == 0) flips++;
            }
        }
        return flips;
    }
}

Approach 2

Level II: Iterative with Built-in Counting

Intuition

Instead of checking every bit manually, we can use built-in bit counting functions to calculate the flips needed for the entire numbers after identifying which bits are incorrect via XOR and AND.

⏱ $O(1)$💾 $O(1)$

java

class Solution {
    public int minFlips(int a, int b, int c) {
        int res = 0;
        for (int i = 0; i < 31; i++) {
            int bitA = (a >> i) & 1, bitB = (b >> i) & 1, bitC = (c >> i) & 1;
            if (bitC == 0) res += bitA + bitB;
            else if (bitA + bitB == 0) res += 1;
        }
        return res;
    }
}

Approach 3

Level III: Optimal (Bitwise Magic)

Intuition

We can use bitwise operators to find all differing bits at once. (a | b) ^ c gives bits that are incorrect. We then handle the cases where c bit is 0 separately as they might require 2 flips per bit.

Thought Process

incorrect = (a | b) ^ c.
must_flip_two = a & b & incorrect.
Flips = Count of set bits in incorrect + Count of set bits in must_flip_two.

Pattern: Composite Bitmasking

⏱ O(1) - Constant number of bitwise operations.💾 O(1) - Constant space.

Detailed Dry Run

a=2(0010), b=6(0110), c=5(0101) a|b = 6 (0110) incorrect = 0110 ^ 0101 = 0011 (bits 0 and 1 are wrong) must_flip_two = 0010 & 0110 & 0011 = 0010 (bit 1 is wrong and both a,b are 1) Total = popcount(0011) + popcount(0010) = 2 + 1 = 3.

java

public class Solution {
    public int minFlips(int a, int b, int c) {
        return Integer.bitCount((a | b) ^ c) + Integer.bitCount(a & b & ((a | b) ^ c));
    }
}

Sum of All Subset XOR Totals

Return the sum of all XOR totals for every subset of nums.

Easy

Examples

Input: nums = [1,3]
Output: 6

Input: nums = [5,1,6]
Output: 28

Approach 1

Level I: Brute Force (Backtracking)

Intuition

Generate all possible $2^n$ subsets, calculate the XOR of each, and sum them up.

Thought Process

Use recursion to explore including or excluding each element.
Maintain a currentXor value through the recursion tree.
Base case: If reached end of array, return currentXor.

Pattern: Subset Generation

⏱ O(2^N) - We visit every subset.💾 O(N) - Recursion depth.

java

public class Solution {
    public int subsetXORSum(int[] nums) {
        return backtrack(nums, 0, 0);
    }
    
    private int backtrack(int[] nums, int index, int currentXor) {
        if (index == nums.length) return currentXor;
        // sum of (XORs including nums[index]) + (XORs excluding nums[index])
        return backtrack(nums, index + 1, currentXor ^ nums[index]) + 
               backtrack(nums, index + 1, currentXor);
    }
}

Approach 2

Level II: Iterative Subset Generation

Intuition

Use a bitmask from 0 to $2^n - 1$ to represent every possible subset of nums. For each mask, calculate the XOR total and add it to the sum.

⏱ $O(N \cdot 2^N)$💾 $O(1)$

java

class Solution {
    public int subsetXORSum(int[] nums) {
        int n = nums.length, total = 0;
        for (int i = 0; i < (1 << n); i++) {
            int current = 0;
            for (int k = 0; k < n; k++) {
                if (((i >> k) & 1) == 1) current ^= nums[k];
            }
            total += current;
        }
        return total;
    }
}

Approach 3

Level III: Optimal (Contribution of Each Bit)

Intuition

For a bit position $i$ , if at least one number in nums has the $i$ -th bit set, then in exactly half of the $2^n$ subsets (i.e., $2^{n-1}$ ), the XOR total will have the $i$ -th bit set. This is because adding a number with the $i$ -th bit set flips the $i$ -th bit of the XOR sum.

Thought Process

Find the bitwise OR of all numbers in the array. This identifies all bit positions that are set in at least one number.
If the $i$ -th bit is set in the OR result, it contributes $2^{i} \cdot 2^{n-1}$ to the total sum.
Result = (OR of all nums) * 2^(n-1).

Pattern: Combinatorial Bit Counting

⏱ O(N) - Single pass to find the bitwise OR.💾 O(1) - Constant space.

Detailed Dry Run

nums = [1, 3], n = 2 OR = 1 | 3 = 3 (binary 11) Sum = 3 * 2^(2-1) = 3 * 2 = 6. Result matches brute force!

java

public class Solution {
    public int subsetXORSum(int[] nums) {
        int res = 0;
        for (int x : nums) res |= x;
        return res << (nums.length - 1);
    }
}

Reverse Pairs

Given an integer array nums, return the number of reverse pairs in the array. A reverse pair is a pair $(i, j)$ such that $0 \leq i < j < nums.length$ and $nums[i] > 2 \cdot nums[j]$ .

Hard

Examples

Input: nums = [1,3,2,3,1]
Output: 2

Input: nums = [2,4,3,5,1]
Output: 3

Approach 1

Level I: Brute Force (Nested Loops)

Intuition

Check every possible pair $(i, j)$ where $i < j$ . If the condition $nums[i] > 2 \cdot nums[j]$ is met, increment the counter.

Thought Process

Use a nested loop $i \in [0, n-1], j \in [i+1, n-1]$ .
Check if $nums[i] > 2 \cdot nums[j]$ .
Return count.

Pattern: All-Pairs Comparison

⏱ O(N^2) - Quadratic complexity.💾 O(1) - No extra space.

java

public class Solution {
    public int reversePairs(int[] nums) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if ((long)nums[i] > 2L * nums[j]) count++;
            }
        }
        return count;
    }
}

Approach 2

Level II: Merge Sort based Counting

Intuition

Similar to counting inversions, we can use merge sort to count reverse pairs. During the merge step, for each element in the left half, we find how many elements in the right half satisfy $nums[i] > 2 \cdot nums[j]$ .

⏱ $O(N \log N)$💾 $O(N)$

java

class Solution {
    public int reversePairs(int[] nums) {
        return mergeSort(nums, 0, nums.length - 1);
    }
    private int mergeSort(int[] nums, int l, int r) {
        if (l >= r) return 0;
        int m = l + (r - l) / 2;
        int res = mergeSort(nums, l, m) + mergeSort(nums, m + 1, r);
        int j = m + 1;
        for (int i = l; i <= m; i++) {
            while (j <= r && (long)nums[i] > 2L * nums[j]) j++;
            res += (j - (m + 1));
        }
        Arrays.sort(nums, l, r + 1);
        return res;
    }
}

Approach 3

Level III: Optimal (Binary Indexed Tree / Fenwick Tree)

Intuition

As we iterate through the array, we want to count how many numbers seen so far are greater than $2 \cdot current$ . A Binary Indexed Tree (BIT) can efficiently handle point updates and prefix sums. Since values can be large, we use coordinate compression on all $nums[i]$ and $2 \cdot nums[i]$ .

Thought Process

Collect all $nums[i]$ and $2 \cdot nums[i]$ and sort them to create distinct ranks (Coordinate Compression).
Iterate through nums from right to left (or left to right with adjustments):
- Query BIT for how many elements are strictly less than $nums[i] / 2$ .
- Update BIT with $nums[i]$ .
This leverages the bitwise structure of indices in the BIT.

Pattern: BIT with Coordinate Compression

⏱ O(N \log N) - Sorting takes $O(N \log N)$, and $N$ BIT operations take $O(N \log N)$.💾 O(N) - To store the BIT and rank map.

java

import java.util.*;

class Solution {
    public int reversePairs(int[] nums) {
        Set<Long> set = new TreeSet<>();
        for (int x : nums) {
            set.add((long)x);
            set.add(2L * x);
        }
        Map<Long, Integer> rank = new HashMap<>();
        int r = 1;
        for (long x : set) rank.put(x, r++);
        
        int[] bit = new int[r];
        int count = 0;
        for (int i = nums.length - 1; i >= 0; i--) {
            count += query(bit, rank.get((long)nums[i]) - 1);
            update(bit, rank.get(2L * nums[i]), 1);
        }
        return count;
    }
    
    private void update(int[] bit, int idx, int val) {
        for (; idx < bit.length; idx += idx & -idx) bit[idx] += val;
    }
    
    private int query(int[] bit, int idx) {
        int res = 0;
        for (; idx > 0; idx -= idx & -idx) res += bit[idx];
        return res;
    }
}

Can I Win

Two players take turns choosing integers from 1 to maxChoosableInteger without reuse. The first to reach desiredTotal wins. Return true if the first player can force a win.

Medium

Examples

Input: maxChoosableInteger = 10, desiredTotal = 11
Output: false

Approach 1

Level I: Recursive Minimax (No Memoization)

Intuition

Explore all possible sequences of choosing numbers. A player wins if they can pick a number that reaches the total, or if there is a number they can pick such that the other player cannot win from the resulting state.

Thought Process

Try choosing each available number $i \in [1, maxChoosableInteger]$ .
If $i \geq currentRemainder$ , you win.
Otherwise, if the other player cannot win from the state (remainder - $i$ , used numbers), you win.
If no such $i$ exists, you lose.

Pattern: Game Theory Recursion

⏱ O(M!) - Where $M$ is `maxChoosableInteger` (all permutations).💾 O(M) - Recursion depth.

java

public class Solution {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (desiredTotal <= 0) return true;
        if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) return false;
        return canWin(desiredTotal, new boolean[maxChoosableInteger + 1]);
    }
    
    private boolean canWin(int remainder, boolean[] used) {
        for (int i = 1; i < used.length; i++) {
            if (!used[i]) {
                if (i >= remainder) return true;
                used[i] = true;
                if (!canWin(remainder - i, used)) {
                    used[i] = false;
                    return true;
                }
                used[i] = false;
            }
        }
        return false;
    }
}

Approach 2

Level II: Recursion with Bitmask only

Intuition

Represent the state of used numbers with a 20-bit integer mask. This is more efficient for passing state through recursion but still suffers from exponential growth without memoization.

⏱ $O(2^M \cdot M)$ (without cache hit logic)💾 $O(M)$

java

class Solution {
    public boolean canIWin(int max, int total) {
        if (total <= 0) return true;
        if (max * (max + 1) / 2 < total) return false;
        return solve(total, 0, max);
    }
    private boolean solve(int rem, int mask, int max) {
        for (int i = 1; i <= max; i++) {
            if (((mask >> (i - 1)) & 1) == 0) {
                if (i >= rem || !solve(rem - i, mask | (1 << (i - 1)), max)) return true;
            }
        }
        return false;
    }
}

Approach 3

Level III: Optimal (Bitmask DP / Memoization)

Intuition

The state of the game is uniquely determined by which integers have been used. Since maxChoosableInteger is at most 20, we can use a bitmask of length 20 to represent the set of used numbers. Memoizing the results of these masks drastically reduces the number of computations.

Thought Process

Use an integer mask where the $i$ -th bit is 1 if number $i$ is used.
Store result of canWin(mask) in a hash map or array.
Base cases: desiredTotal <= 0 or sum check.

Pattern: State Compression DP

⏱ O(2^M \cdot M) - $2^M$ possible states, each state takes $O(M)$ to compute transitions.💾 O(2^M) - To store the memoization table.

java

import java.util.*;

public class Solution {
    Map<Integer, Boolean> memo = new HashMap<>();
    
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (desiredTotal <= 0) return true;
        if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) return false;
        return solve(maxChoosableInteger, desiredTotal, 0);
    }
    
    private boolean solve(int max, int rem, int mask) {
        if (memo.containsKey(mask)) return memo.get(mask);
        for (int i = 1; i <= max; i++) {
            int curr = (1 << (i - 1));
            if ((mask & curr) == 0) {
                if (i >= rem || !solve(max, rem - i, mask | curr)) {
                    memo.put(mask, true);
                    return true;
                }
            }
        }
        memo.put(mask, false);
        return false;
    }
}

Maximum AND Sum of Array

Place n integers into numSlots slots (max 2 per slot). The AND sum is the sum of (nums[i] & slotNumber). Return the maximum possible AND sum.

Hard

Examples

Input: nums = [1,2,3,4,5,6], numSlots = 3
Output: 9

Approach 1

Level I: Brute Force (Recursion)

Intuition

Try all possible placements of the $n$ integers into the $numSlots$ slots. Each slot can take up to 2 integers. This is an exhaustive search of the solution space.

⏱ $O(numSlots^N)$💾 $O(N)$

java

class Solution {
    public int maximumANDSum(int[] nums, int numSlots) {
        return solve(0, new int[numSlots + 1], nums);
    }
    private int solve(int idx, int[] counts, int[] nums) {
        if (idx == nums.length) return 0;
        int max = 0;
        for (int i = 1; i < counts.length; i++) {
            if (counts[i] < 2) {
                counts[i]++;
                max = Math.max(max, (nums[idx] & i) + solve(idx + 1, counts, nums));
                counts[i]--;
            }
        }
        return max;
    }
}

Approach 2

Level II: Greedy / Simple DP

Intuition

Identify that the problem has overlapping subproblems. Even without a full ternary mask, we can use a simpler memoization based on the current counts array (converted to a string or tuple) to avoid redundant work.

⏱ $O(N \cdot 3^{numSlots})$💾 $O(N \cdot 3^{numSlots})$

java

class Solution {
    Map<String, Integer> memo = new HashMap<>();
    public int maximumANDSum(int[] nums, int numSlots) {
        return solve(0, new int[numSlots + 1], nums);
    }
    private int solve(int idx, int[] counts, int[] nums) {
        if (idx == nums.length) return 0;
        String key = idx + Arrays.toString(counts);
        if (memo.containsKey(key)) return memo.get(key);
        int max = 0;
        for (int i = 1; i < counts.length; i++) {
            if (counts[i] < 2) {
                counts[i]++;
                max = Math.max(max, (nums[idx] & i) + solve(idx + 1, counts, nums));
                counts[i]--;
            }
        }
        memo.put(key, max);
        return max;
    }
}

Approach 3

Level III: Bitmask DP (Ternary / Base-3)

Intuition

Since each slot can hold up to 2 integers, we can represent the state of the slots using a base-3 integer. In this integer, the $i$ -th digit (in base 3) represents the number of elements in slot $i+1$ (0, 1, or 2).

Thought Process

Use a recursive function solve(index, mask) where index is the current number in nums we are placing.
The mask is a base-3 representation of slot occupancies.
For each slot $j \in [1, numSlots]$ $j \in [1, n u m Sl o t s]$ :
- Check if slot $j$ has $< 2$ items.
- If yes, place nums[index] in slot $j$ , update mask, and take the results.

Pattern: Base-N Bitmasking

⏱ O(N \cdot 3^S) - Where $N$ is `nums.length` and $S$ is `numSlots`.💾 O(3^S) - Memoization table.

java

public class Solution {
    int[] memo;
    int[] pow3;

    public int maximumANDSum(int[] nums, int numSlots) {
        pow3 = new int[numSlots + 1];
        pow3[0] = 1;
        for (int i = 1; i <= numSlots; i++) pow3[i] = pow3[i - 1] * 3;
        memo = new int[pow3[numSlots]];
        return solve(0, 0, nums, numSlots);
    }

    private int solve(int idx, int mask, int[] nums, int numSlots) {
        if (idx == nums.length) return 0;
        if (memo[mask] > 0) return memo[mask] - 1;
        int res = 0;
        for (int i = 0; i < numSlots; i++) {
            int slotVal = (mask / pow3[i]) % 3;
            if (slotVal < 2) {
                res = Math.max(res, (nums[idx] & (i + 1)) + solve(idx + 1, mask + pow3[i], nums, numSlots));
            }
        }
        memo[mask] = res + 1;
        return res;
    }
}

← Previous TopicUnion Find

Next Topic →Design

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.