Course4all

Bit Manipulation

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Bit Manipulation.

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

OperatorSymbolRule
AND&1 & 1 = 1, otherwise 0. (Masking)
OR``
XOR^1 ^ 0 = 1, 1 ^ 1 = 0. (Toggling/Canceling)
NOT~Flips all bits.
Left Shift<<xcdot2nx \\cdot 2^n
Right Shift>>x/2nx / 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: aoplusa=0a \\oplus a = 0 and aoplus0=aa \\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)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: xoplusx=0x \\oplus x = 0 and xoplus0=xx \\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==2xn == 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 230=10737418242^{30} = 1073741824. If n is a power of two, it must be a divisor of 2302^{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∈[0,31]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⊕yx \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 xx and yy.
⏱ $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

  1. Initialize res = left.
  2. Iterate i from left + 1 to right.
  3. res &= i.
  4. 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

  1. While right > left:
    • right = right & (right - 1) (clears the rightmost set bit).
  2. 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

  1. Initialize a counter count = 0.
  2. Loop 32 times (for a 32-bit integer):
    • Check if the last bit is 1: (n & 1) == 1.
    • If yes, increment count.
    • Right shift nn by 1: n >>= 1.
  3. 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 nn.

Thought Process

  1. While n≠0n \neq 0:
    • Set n = n \text{ & } (n - 1). This removes exactly one '1' bit.
    • Increment count.
  2. 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)
Iterationn (Before)n-1n & (n-1)count
11100 (12)1011 (11)1000 (8)1
21000 (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

  1. Initialize res = 0.
  2. 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.
  3. 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

  1. Swap bits 1-by-1: n = ((n & 0xAAAAAAAA) >>> 1) | ((n & 0x55555555) << 1)
  2. Swap bits 2-by-2: n = ((n & 0xCCCCCCCC) >>> 2) | ((n & 0x33333333) << 2)
  3. Swap bits 4-by-4: n = ((n & 0xF0F0F0F0) >>> 4) | ((n & 0x0F0F0F0F) << 4)
  4. Swap bits 8-by-8: n = ((n & 0xFF00FF00) >>> 8) | ((n & 0x00FF00FF) << 8)
  5. 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

  1. Initialize res = 0, carry = 0.
  2. For i from 0 to 31:
    • Get ii-th bits of a and b.
    • sum = bitA ^ bitB ^ carry.
    • carry = (bitA & bitB) | (carry & (bitA ^ bitB)).
    • Set ii-th bit of res to sum.
  3. 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

  1. a ^ b gives the sum bits where no carry is involved.
  2. a & b gives the bits where a carry is generated.
  3. Shift the carry left by 1 to add it to the next significant bit.
  4. 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 ii where nums[i] != i is the missing number. If all match, the missing number is nn.

Thought Process

  1. Sort nums in ascending order.
  2. Iterate ii from 00 to n−1n - 1:
    • If nums[i] != i, return i.
  3. 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 nn numbers is n(n+1)2\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⊕x=0x \oplus x = 0). If we XOR all numbers in the range [0,n][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

  1. Initialize missing = n (or 0).
  2. Iterate through the array:
    • missing ^= i ^ nums[i]
  3. 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

  1. Use three nested loops for i, j, and k.
  2. In the innermost loop, calculate XOR for a and b.
  3. 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)(i, k) such that P[i]==P[k+1]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==ba == b is equivalent to arr[i]⊕...⊕arr[k]=0arr[i] \oplus ... \oplus arr[k] = 0. Using prefix XOR array PP where P[x]=arr[0]⊕...⊕arr[x−1]P[x] = arr[0] \oplus ... \oplus arr[x-1], the XOR of arr[i...k]arr[i...k] is P[k+1]⊕P[i]P[k+1] \oplus P[i]. We need P[k+1]==P[i]P[k+1] == P[i]. If found, all j∈(i,k]j \in (i, k] are valid.

Thought Process

  1. Calculate prefix XOR array prefix.
  2. Iterate through all pairs (i,k)(i, k) where i<ki < 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 2n2^n integers where:
  • Every integer is in the inclusive range [0,2n−1][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

  1. Start with 0.
  2. Try flipping each of the nn bits.
  3. If the result is not visited, move to it and recurse.
  4. 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 nn bits can be built from the Gray code for n−1n-1 bits by reflecting the sequence and adding a leading 1 (bit n−1n-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 ii-th number in the Gray code sequence can be generated using the formula G(i)=i⊕(i/2)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

  1. The total number of elements is 2n2^n.
  2. For each index ii from 0 to 2n−12^n - 1:
    • Calculate i ^ (i >> 1).
  3. 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

  1. Use a seen hash set to track substrings.
  2. Use a repeated hash set to collect result strings.
  3. 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)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)O(1) per character.

Thought Process

  1. Map A=0, C=1, G=2, T=3.
  2. Maintain a 20-bit sliding window.
  3. 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

  1. Nested loop (i,j)(i, j) for all pairs.
  2. 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

  1. Precompute bitmasks for all words.
  2. Nested loop (i,j)(i, j) and check (masks[i] & masks[j]) == 0.
  3. 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≤i≤j<n0 \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)(i, j) and calculate their XOR sum. Track the maximum value found.

Thought Process

  1. Initialize maxResult = 0.
  2. Nested loop through nums.
  3. maxResult = max(maxResult, nums[i] ^ nums[j]).
  4. 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 ii (from MSB to LSB), we check if there exists a pair of numbers whose ii-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 XX, we want to find another number YY 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

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

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

  1. Handle edge cases (overflow for INT_MIN).
  2. Determine sign of result.
  3. Take absolute values of dividend and divisor.
  4. Loop while dividend >= divisor:
    • dividend -= divisor.
    • count++.
  5. 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

  1. While dividend >= divisor:
    • Find the largest kk such that divisor << k <= dividend.
    • dividend -= (divisor << k).
    • quotient += (1 << k).
  2. This uses the property that B⋅2kB \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

  1. Initialize totalDist = 0.
  2. For each pair (i,j)(i, j) where i<ji < j:
    • Calculate Hamming distance: Integer.bitCount(nums[i] ^ nums[j]).
    • Add to totalDist.
  3. 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 ii, if kk numbers have the ii-th bit set to 1, and n−kn-k numbers have it set to 0, then there are k⋅(n−k)k \cdot (n-k) pairs that differ at this position.

Thought Process

  1. Initialize total = 0.
  2. For each bit position 00 to 3131:
    • Count numbers kk with ii-th bit set.
    • total += k * (n - k).
  3. 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

  1. For each bit position ii (0 to 31):
    • If ii-th bit of c is 0:
      • Both ii-th bits of a and b must be 0. Add their sum to flips.
    • If ii-th bit of c is 1:
      • At least one of ii-th bits of a or b must be 1. If both are 0, add 1 to flips.
  2. 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

  1. incorrect = (a | b) ^ c.
  2. must_flip_two = a & b & incorrect.
  3. 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 2n2^n subsets, calculate the XOR of each, and sum them up.

Thought Process

  1. Use recursion to explore including or excluding each element.
  2. Maintain a currentXor value through the recursion tree.
  3. 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 2n−12^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 ii, if at least one number in nums has the ii-th bit set, then in exactly half of the 2n2^n subsets (i.e., 2n−12^{n-1}), the XOR total will have the ii-th bit set. This is because adding a number with the ii-th bit set flips the ii-th bit of the XOR sum.

Thought Process

  1. Find the bitwise OR of all numbers in the array. This identifies all bit positions that are set in at least one number.
  2. If the ii-th bit is set in the OR result, it contributes 2i⋅2n−12^{i} \cdot 2^{n-1} to the total sum.
  3. 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)(i, j) such that 0≤i<j<nums.length0 \leq i < j < nums.length and nums[i]>2⋅nums[j]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)(i, j) where i<ji < j. If the condition nums[i]>2⋅nums[j]nums[i] > 2 \cdot nums[j] is met, increment the counter.

Thought Process

  1. Use a nested loop i∈[0,n−1],j∈[i+1,n−1]i \in [0, n-1], j \in [i+1, n-1].
  2. Check if nums[i]>2⋅nums[j]nums[i] > 2 \cdot nums[j].
  3. 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⋅nums[j]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⋅current2 \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]nums[i] and 2⋅nums[i]2 \cdot nums[i].

Thought Process

  1. Collect all nums[i]nums[i] and 2⋅nums[i]2 \cdot nums[i] and sort them to create distinct ranks (Coordinate Compression).
  2. 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]/2nums[i] / 2.
    • Update BIT with nums[i]nums[i].
  3. 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

  1. Try choosing each available number i∈[1,maxChoosableInteger]i \in [1, maxChoosableInteger].
  2. If i≥currentRemainderi \geq currentRemainder, you win.
  3. Otherwise, if the other player cannot win from the state (remainder - ii, used numbers), you win.
  4. If no such ii 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

  1. Use an integer mask where the ii-th bit is 1 if number ii is used.
  2. Store result of canWin(mask) in a hash map or array.
  3. 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 nn integers into the numSlotsnumSlots 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 ii-th digit (in base 3) represents the number of elements in slot i+1i+1 (0, 1, or 2).

Thought Process

  1. Use a recursive function solve(index, mask) where index is the current number in nums we are placing.
  2. The mask is a base-3 representation of slot occupancies.
  3. For each slot j∈[1,numSlots]j \in [1, numSlots]:
    • Check if slot jj has <2< 2 items.
    • If yes, place nums[index] in slot jj, 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;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly

Explore More DSA Topics

Recommended Topic

Design

Read Lesson
Recommended Topic

Arrays & Hashing

Read Lesson
Recommended Topic

Two Pointers

Read Lesson
Recommended Topic

Sliding Window

Read Lesson
← Previous TopicUnion Find
Next Topic →Design