Bit Manipulation & Cyclic Sort Patterns

Low-level operations and in-place sorting for constrained problems

These two patterns are essential for optimizing space and time complexity in coding interviews. Bit manipulation leverages binary representations for lightning-fast operations, while cyclic sort provides an elegant O(n) solution for problems involving numbers in a given range.

Bit Manipulation Pattern

Why Bit Manipulation Matters

Every piece of data in a computer is ultimately represented as bits (0s and 1s). Understanding bit manipulation provides:

Hardware-level speed: Operations execute in a single CPU cycle
Space efficiency: Pack multiple values into a single integer
Elegant solutions: Replace complex logic with simple bit operations
Interview success: Common in FAANG interviews for optimization questions

Core Bitwise Operators

Operator	Symbol	Description	Example
AND	`&`	1 if both bits are 1	`5 & 3 = 1` (101 & 011 = 001)
OR	`\|`	1 if either bit is 1	`5 \| 3 = 7` (101 \| 011 = 111)
XOR	`^`	1 if bits are different	`5 ^ 3 = 6` (101 ^ 011 = 110)
NOT	`~`	Inverts all bits	`~5 = -6` (inverts 101)
Left Shift	`<<`	Shift bits left, fill with 0	`5 << 1 = 10` (101 -> 1010)
Right Shift	`>>`	Shift bits right	`5 >> 1 = 2` (101 -> 10)

Essential Bit Operations

Operation	Code	Use Case
Check if bit i is set	`n & (1 << i)`	Test if bit i is 1
Set bit i	`n \| (1 << i)`	Turn on bit i
Clear bit i	`n & ~(1 << i)`	Turn off bit i
Toggle bit i	`n ^ (1 << i)`	Flip bit i
Check power of 2	`n & (n-1) == 0`	True if single bit set
Get lowest set bit	`n & (-n)`	Isolate rightmost 1-bit
Clear lowest set bit	`n & (n-1)`	Turn off rightmost 1-bit
Check if even/odd	`n & 1`	0 if even, 1 if odd
Multiply by 2^k	`n << k`	Left shift by k
Divide by 2^k	`n >> k`	Right shift by k

XOR Properties

XOR is particularly powerful for solving interview problems:

a ^ a = 0          // Any number XOR itself is 0
a ^ 0 = a          // Any number XOR 0 is itself
a ^ b ^ a = b      // XOR is self-inverse
a ^ b = b ^ a      // Commutative property
(a ^ b) ^ c = a ^ (b ^ c)  // Associative property

Key Insight: XOR cancels out pairs, making it perfect for finding unique elements.

Template Code

PythonJava

python

# ============================================
# SINGLE NUMBER - Find element appearing once
# ============================================
def single_number(nums: list[int]) -> int:
    """
    All elements appear twice except one.
    XOR cancels pairs: a ^ a = 0
    Time: O(n), Space: O(1)
    """
    result = 0
    for num in nums:
        result ^= num
    return result

# Example: [4, 1, 2, 1, 2] -> 4
# 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1^1) ^ (2^2) = 4 ^ 0 ^ 0 = 4


# ============================================
# COUNT SET BITS (Brian Kernighan's Algorithm)
# ============================================
def count_bits(n: int) -> int:
    """
    Count number of 1-bits in binary representation.
    n & (n-1) clears the lowest set bit.
    Time: O(number of set bits)
    """
    count = 0
    while n:
        n &= (n - 1)  # Clear lowest set bit
        count += 1
    return count

# Alternative using built-in
def count_bits_builtin(n: int) -> int:
    return bin(n).count('1')


# ============================================
# CHECK IF POWER OF TWO
# ============================================
def is_power_of_two(n: int) -> bool:
    """
    Power of 2 has exactly one bit set.
    n & (n-1) == 0 checks for single set bit.
    """
    return n > 0 and (n & (n - 1)) == 0

# Example: 8 = 1000, 8-1 = 0111, 1000 & 0111 = 0000


# ============================================
# MISSING NUMBER (XOR approach)
# ============================================
def missing_number(nums: list[int]) -> int:
    """
    Array [0, n] with one number missing.
    XOR all numbers with all indices.
    """
    result = len(nums)
    for i, num in enumerate(nums):
        result ^= i ^ num
    return result


# ============================================
# SWAP WITHOUT TEMP VARIABLE
# ============================================
def swap_xor(a: int, b: int) -> tuple[int, int]:
    """
    Swap two numbers using XOR (interview trick).
    """
    a ^= b  # a now contains a ^ b
    b ^= a  # b = b ^ (a ^ b) = a
    a ^= b  # a = (a ^ b) ^ a = b
    return a, b


# ============================================
# REVERSE BITS
# ============================================
def reverse_bits(n: int) -> int:
    """
    Reverse 32-bit unsigned integer.
    """
    result = 0
    for _ in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result


# ============================================
# SINGLE NUMBER II - Element appears once, others three times
# ============================================
def single_number_ii(nums: list[int]) -> int:
    """
    Count bits at each position mod 3.
    Time: O(32n), Space: O(1)
    """
    result = 0
    for i in range(32):
        bit_sum = 0
        for num in nums:
            bit_sum += (num >> i) & 1
        if bit_sum % 3:
            result |= (1 << i)
    # Handle negative numbers in Python
    if result >= 2**31:
        result -= 2**32
    return result


# ============================================
# SINGLE NUMBER III - Two elements appear once
# ============================================
def single_number_iii(nums: list[int]) -> list[int]:
    """
    Find two numbers that appear only once.
    1. XOR all to get a ^ b
    2. Find differing bit to split into two groups
    3. XOR each group separately
    """
    xor_all = 0
    for num in nums:
        xor_all ^= num

    # Find rightmost set bit (where a and b differ)
    diff_bit = xor_all & (-xor_all)

    a, b = 0, 0
    for num in nums:
        if num & diff_bit:
            a ^= num
        else:
            b ^= num

    return [a, b]


# ============================================
# GENERATE ALL SUBSETS USING BITMASK
# ============================================
def subsets(nums: list[int]) -> list[list[int]]:
    """
    Generate all 2^n subsets using bit manipulation.
    Each bit represents whether to include element.
    """
    n = len(nums)
    result = []

    for mask in range(1 << n):  # 0 to 2^n - 1
        subset = []
        for i in range(n):
            if mask & (1 << i):  # Check if bit i is set
                subset.append(nums[i])
        result.append(subset)

    return result

java

// SINGLE NUMBER
int singleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) result ^= num;
    return result;
}

// COUNT SET BITS (Brian Kernighan)
int countBits(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);  // clear lowest set bit
        count++;
    }
    return count;
}

// CHECK IF POWER OF TWO
boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

// MISSING NUMBER
int missingNumber(int[] nums) {
    int result = nums.length;
    for (int i = 0; i < nums.length; i++) result ^= i ^ nums[i];
    return result;
}

// REVERSE BITS
int reverseBits(int n) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);
        n >>>= 1;  // unsigned right shift
    }
    return result;
}

// SINGLE NUMBER II
int singleNumberII(int[] nums) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        int bitSum = 0;
        for (int num : nums) bitSum += (num >> i) & 1;
        if (bitSum % 3 != 0) result |= (1 << i);
    }
    return result;
}

// SINGLE NUMBER III
int[] singleNumberIII(int[] nums) {
    int xorAll = 0;
    for (int num : nums) xorAll ^= num;
    int diffBit = xorAll & (-xorAll);
    int a = 0, b = 0;
    for (int num : nums) {
        if ((num & diffBit) != 0) a ^= num;
        else b ^= num;
    }
    return new int[]{a, b};
}

// GENERATE ALL SUBSETS USING BITMASK
List<List<Integer>> subsets(int[] nums) {
    int n = nums.length;
    List<List<Integer>> result = new ArrayList<>();
    for (int mask = 0; mask < (1 << n); mask++) {
        List<Integer> subset = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) subset.add(nums[i]);
        }
        result.add(subset);
    }
    return result;
}

Complexity Summary for Bit Manipulation Functions

single_number: Time O(n), Space O(1) - XOR all elements once
count_bits: Time O(k) where k is number of set bits, Space O(1)
is_power_of_two: Time O(1), Space O(1) - Single bit operation
missing_number: Time O(n), Space O(1) - XOR all indices and values
reverse_bits: Time O(32) = O(1), Space O(1) - Fixed 32 iterations
single_number_ii: Time O(32n) = O(n), Space O(1) - Check each of 32 bits
single_number_iii: Time O(n), Space O(1) - Two passes through array
subsets: Time O(n * 2^n), Space O(n * 2^n) - Generate all 2^n subsets

Classic Problems

Problem	Difficulty	Key Technique
Single Number	Easy	XOR all elements
Single Number II	Medium	Bit counting mod 3
Single Number III	Medium	XOR + split by diff bit
Missing Number	Easy	XOR with indices
Reverse Bits	Easy	Bit-by-bit reversal
Power of Two	Easy	`n & (n-1) == 0`
Counting Bits	Easy	Dynamic programming with bits
Hamming Distance	Easy	XOR + count set bits
Number of 1 Bits	Easy	Brian Kernighan's algorithm
Sum of Two Integers	Medium	XOR for sum, AND for carry
Subsets	Medium	Bitmask enumeration

Cyclic Sort Pattern

Concept

Cyclic Sort is an elegant in-place sorting algorithm designed specifically for arrays containing numbers in a contiguous range (typically 1 to n or 0 to n-1).

Key Insight: If an array contains numbers from 1 to n, each number x should be at index x-1. We can place each number in its correct position by swapping.

When to Use Cyclic Sort

Use this pattern when:

Array contains numbers in range [1, n] or [0, n-1]
You need to find missing or duplicate numbers
O(1) space constraint is required
The problem involves "should be at index" relationship

Cannot use when:

Numbers are outside the expected range
Floating point numbers are involved
Array modification is not allowed

Algorithm Characteristics

Property	Value
Time Complexity	O(n)
Space Complexity	O(1)
In-place	Yes
Stable	No

Template Code

PythonJava

python

# ============================================
# BASIC CYCLIC SORT
# ============================================
def cyclic_sort(nums: list[int]) -> list[int]:
    """
    Sort array containing numbers 1 to n.
    Place each number at index (number - 1).
    Time: O(n), Space: O(1)
    """
    i = 0
    while i < len(nums):
        correct_idx = nums[i] - 1  # Where nums[i] should be
        if nums[i] != nums[correct_idx]:
            # Swap to correct position
            nums[i], nums[correct_idx] = nums[correct_idx], nums[i]
        else:
            i += 1  # Already in place or duplicate
    return nums

# Example: [3, 1, 5, 4, 2]
# i=0: 3 should be at index 2, swap -> [5, 1, 3, 4, 2]
# i=0: 5 should be at index 4, swap -> [2, 1, 3, 4, 5]
# i=0: 2 should be at index 1, swap -> [1, 2, 3, 4, 5]
# i=0: 1 is at correct index, i++
# ... continue until sorted


# ============================================
# FIND MISSING NUMBER
# ============================================
def find_missing(nums: list[int]) -> int:
    """
    Array [1, n] with one number missing.
    Sort cyclically, then find misplaced element.
    """
    n = len(nums)
    i = 0

    while i < n:
        correct_idx = nums[i] - 1
        # Only swap if within range and not at correct position
        if 0 <= correct_idx < n and nums[i] != nums[correct_idx]:
            nums[i], nums[correct_idx] = nums[correct_idx], nums[i]
        else:
            i += 1

    # Find the missing number
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1

    return n + 1  # All in place, missing is n+1


# ============================================
# FIND ALL MISSING NUMBERS (LC 448)
# ============================================
def find_all_missing(nums: list[int]) -> list[int]:
    """
    Array of n integers where 1 <= nums[i] <= n.
    Some elements appear twice, some don't appear.
    Find all that don't appear.
    """
    n = len(nums)
    i = 0

    while i < n:
        correct_idx = nums[i] - 1
        if nums[i] != nums[correct_idx]:
            nums[i], nums[correct_idx] = nums[correct_idx], nums[i]
        else:
            i += 1

    missing = []
    for i in range(n):
        if nums[i] != i + 1:
            missing.append(i + 1)

    return missing


# ============================================
# FIND DUPLICATE NUMBER (LC 287)
# ============================================
def find_duplicate(nums: list[int]) -> int:
    """
    Array of n+1 integers where each is in [1, n].
    One number appears more than once.
    """
    i = 0
    while i < len(nums):
        if nums[i] != i + 1:
            correct_idx = nums[i] - 1
            if nums[i] == nums[correct_idx]:
                return nums[i]  # Found duplicate!
            nums[i], nums[correct_idx] = nums[correct_idx], nums[i]
        else:
            i += 1
    return -1


# ============================================
# FIND ALL DUPLICATES (LC 442)
# ============================================
def find_all_duplicates(nums: list[int]) -> list[int]:
    """
    Array of n integers where 1 <= nums[i] <= n.
    Some elements appear twice, others once.
    Find all that appear twice.
    """
    n = len(nums)
    i = 0

    while i < n:
        correct_idx = nums[i] - 1
        if nums[i] != nums[correct_idx]:
            nums[i], nums[correct_idx] = nums[correct_idx], nums[i]
        else:
            i += 1

    duplicates = []
    for i in range(n):
        if nums[i] != i + 1:
            duplicates.append(nums[i])

    return duplicates


# ============================================
# FIRST MISSING POSITIVE (LC 41) - Hard
# ============================================
def first_missing_positive(nums: list[int]) -> int:
    """
    Find smallest missing positive integer.
    Key: Answer must be in [1, n+1].
    Ignore non-positive and numbers > n.
    """
    n = len(nums)
    i = 0

    while i < n:
        correct_idx = nums[i] - 1
        # Only process if in valid range [1, n]
        if 0 < nums[i] <= n and nums[i] != nums[correct_idx]:
            nums[i], nums[correct_idx] = nums[correct_idx], nums[i]
        else:
            i += 1

    # First position where nums[i] != i+1 is answer
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1

    return n + 1


# ============================================
# SET MISMATCH (LC 645)
# ============================================
def find_error_nums(nums: list[int]) -> list[int]:
    """
    Array [1, n] with one duplicate and one missing.
    Return [duplicate, missing].
    """
    n = len(nums)
    i = 0

    while i < n:
        correct_idx = nums[i] - 1
        if nums[i] != nums[correct_idx]:
            nums[i], nums[correct_idx] = nums[correct_idx], nums[i]
        else:
            i += 1

    # Find the number at wrong position
    for i in range(n):
        if nums[i] != i + 1:
            return [nums[i], i + 1]

    return []


# ============================================
# CYCLIC SORT FOR 0-INDEXED RANGE [0, n-1]
# ============================================
def cyclic_sort_zero_indexed(nums: list[int]) -> list[int]:
    """
    Sort array containing numbers 0 to n-1.
    Place each number at its own index.
    """
    i = 0
    while i < len(nums):
        correct_idx = nums[i]  # For 0-indexed, number IS the index
        if nums[i] < len(nums) and nums[i] != nums[correct_idx]:
            nums[i], nums[correct_idx] = nums[correct_idx], nums[i]
        else:
            i += 1
    return nums

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198

java

// ============================================
// BASIC CYCLIC SORT
// ============================================
int[] cyclicSort(int[] nums) {
    // Sort array containing numbers 1 to n.
    // Place each number at index (number - 1).
    // Time: O(n), Space: O(1)
    int i = 0;
    while (i < nums.length) {
        int correctIdx = nums[i] - 1; // where nums[i] should be
        if (nums[i] != nums[correctIdx]) {
            int tmp = nums[i];
            nums[i] = nums[correctIdx];
            nums[correctIdx] = tmp;
        } else {
            i++;
        }
    }
    return nums;
}

// ============================================
// FIND MISSING NUMBER
// ============================================
int findMissing(int[] nums) {
    // Array [1, n] with one number missing.
    int n = nums.length;
    int i = 0;
    while (i < n) {
        int correctIdx = nums[i] - 1;
        if (correctIdx >= 0 && correctIdx < n && nums[i] != nums[correctIdx]) {
            int tmp = nums[i];
            nums[i] = nums[correctIdx];
            nums[correctIdx] = tmp;
        } else {
            i++;
        }
    }
    for (int j = 0; j < n; j++) {
        if (nums[j] != j + 1) return j + 1;
    }
    return n + 1;
}

// ============================================
// FIND ALL MISSING NUMBERS (LC 448)
// ============================================
List<Integer> findAllMissing(int[] nums) {
    int n = nums.length;
    int i = 0;
    while (i < n) {
        int correctIdx = nums[i] - 1;
        if (nums[i] != nums[correctIdx]) {
            int tmp = nums[i];
            nums[i] = nums[correctIdx];
            nums[correctIdx] = tmp;
        } else {
            i++;
        }
    }
    List<Integer> missing = new ArrayList<>();
    for (int j = 0; j < n; j++) {
        if (nums[j] != j + 1) missing.add(j + 1);
    }
    return missing;
}

// ============================================
// FIND DUPLICATE NUMBER (LC 287)
// ============================================
int findDuplicate(int[] nums) {
    int i = 0;
    while (i < nums.length) {
        if (nums[i] != i + 1) {
            int correctIdx = nums[i] - 1;
            if (nums[i] == nums[correctIdx]) return nums[i]; // found duplicate
            int tmp = nums[i];
            nums[i] = nums[correctIdx];
            nums[correctIdx] = tmp;
        } else {
            i++;
        }
    }
    return -1;
}

// ============================================
// FIND ALL DUPLICATES (LC 442)
// ============================================
List<Integer> findAllDuplicates(int[] nums) {
    int n = nums.length;
    int i = 0;
    while (i < n) {
        int correctIdx = nums[i] - 1;
        if (nums[i] != nums[correctIdx]) {
            int tmp = nums[i];
            nums[i] = nums[correctIdx];
            nums[correctIdx] = tmp;
        } else {
            i++;
        }
    }
    List<Integer> duplicates = new ArrayList<>();
    for (int j = 0; j < n; j++) {
        if (nums[j] != j + 1) duplicates.add(nums[j]);
    }
    return duplicates;
}

// ============================================
// FIRST MISSING POSITIVE (LC 41) - Hard
// ============================================
int firstMissingPositive(int[] nums) {
    int n = nums.length;
    int i = 0;
    while (i < n) {
        int correctIdx = nums[i] - 1;
        if (nums[i] > 0 && nums[i] <= n && nums[i] != nums[correctIdx]) {
            int tmp = nums[i];
            nums[i] = nums[correctIdx];
            nums[correctIdx] = tmp;
        } else {
            i++;
        }
    }
    for (int j = 0; j < n; j++) {
        if (nums[j] != j + 1) return j + 1;
    }
    return n + 1;
}

// ============================================
// SET MISMATCH (LC 645)
// ============================================
int[] findErrorNums(int[] nums) {
    int n = nums.length;
    int i = 0;
    while (i < n) {
        int correctIdx = nums[i] - 1;
        if (nums[i] != nums[correctIdx]) {
            int tmp = nums[i];
            nums[i] = nums[correctIdx];
            nums[correctIdx] = tmp;
        } else {
            i++;
        }
    }
    for (int j = 0; j < n; j++) {
        if (nums[j] != j + 1) return new int[]{nums[j], j + 1};
    }
    return new int[]{};
}

// ============================================
// CYCLIC SORT FOR 0-INDEXED RANGE [0, n-1]
// ============================================
int[] cyclicSortZeroIndexed(int[] nums) {
    int i = 0;
    while (i < nums.length) {
        int correctIdx = nums[i]; // for 0-indexed, number IS the index
        if (nums[i] < nums.length && nums[i] != nums[correctIdx]) {
            int tmp = nums[i];
            nums[i] = nums[correctIdx];
            nums[correctIdx] = tmp;
        } else {
            i++;
        }
    }
    return nums;
}

Complexity Summary for Cyclic Sort Functions

cyclic_sort: Time O(n), Space O(1) - Each element swapped at most once to its correct position
find_missing: Time O(n), Space O(1) - Cyclic sort phase + linear scan
find_all_missing: Time O(n), Space O(1) extra - Only output array uses additional space
find_duplicate: Time O(n), Space O(1) - Early termination when duplicate found
find_all_duplicates: Time O(n), Space O(1) extra - Only output array uses additional space
first_missing_positive: Time O(n), Space O(1) - Handles negative and out-of-range values
find_error_nums: Time O(n), Space O(1) - Returns both duplicate and missing in single pass

Classic Problems

Problem	Difficulty	Key Variation
Missing Number	Easy	Find one missing in [0,n]
Find All Missing Numbers	Easy	Find all missing
Find the Duplicate	Medium	Find one duplicate
Find All Duplicates	Medium	Find all duplicates
First Missing Positive	Hard	Handle negatives, > n
Set Mismatch	Easy	Find both duplicate and missing

Visual Example: Cyclic Sort Process

Input: [3, 1, 5, 4, 2]
Goal: Place each number at index (number - 1)

Step 1: i=0, nums[0]=3, should be at index 2
        Swap positions 0 and 2
        [5, 1, 3, 4, 2]

Step 2: i=0, nums[0]=5, should be at index 4
        Swap positions 0 and 4
        [2, 1, 3, 4, 5]

Step 3: i=0, nums[0]=2, should be at index 1
        Swap positions 0 and 1
        [1, 2, 3, 4, 5]

Step 4: i=0, nums[0]=1, correct position!
        Move to i=1

Step 5: i=1, nums[1]=2, correct position!
        Move to i=2
        ... (all remaining are correct)

Output: [1, 2, 3, 4, 5]

Interview Applications

Bit Manipulation in Interviews

Google frequently asks bit manipulation questions to assess:

Understanding of computer fundamentals
Ability to optimize space-constrained solutions
Knowledge of binary representation tricks

Common Interview Questions:

UTF-8 Validation: Validate if array represents valid UTF-8 encoding
Maximum XOR of Two Numbers: Use trie + bit manipulation
Counting Bits: Dynamic programming with bit properties
Bitwise AND of Numbers Range: Find common prefix bits

Cyclic Sort in Interviews

The cyclic sort pattern appears in technical interviews for:

Array manipulation with space constraints
Finding missing/duplicate elements in O(1) space
Problems requiring in-place transformations

Common Interview Questions:

First Missing Positive: Classic Google question - find smallest missing positive in O(n) time, O(1) space
Find All Duplicates: Without extra space
Set Mismatch: Identify both duplicate and missing number

Interview Tips

For Bit Manipulation:

Always visualize binary representations on paper
Remember common identities: n & (n-1) clears lowest bit, n & -n isolates lowest bit
XOR is your friend for finding unique elements
Think about how bits propagate through operations

For Cyclic Sort:

Recognize the pattern: "numbers 1 to n in array of size n"
The swap condition nums[i] != nums[correct_idx] handles duplicates
After sorting, scan for mismatches to find answers
Handle edge cases: numbers outside range, zero-indexed vs one-indexed

Complexity Comparison

Approach	Time	Space	When to Use
Hash Set	O(n)	O(n)	When modification not allowed
Sorting	O(n log n)	O(1)	When order doesn't matter
Cyclic Sort	O(n)	O(1)	When range is [1,n] or [0,n-1]
Bit Manipulation	O(n)	O(1)	When elements have XOR property

Practice Problems by Difficulty

Easy

Single Number (LeetCode 136)

Problem: Every element appears twice except one. Find the single element.

Key Insight: XOR of a number with itself is 0. XOR of all elements cancels pairs, leaving the single number.

Approach: Initialize result = 0, XOR all elements: result ^= num for each num in array.

Complexity: Time O(n), Space O(1)

Missing Number (LeetCode 268)

Problem: Array contains n distinct numbers from range [0, n]. Find the missing one.

Key Insight: XOR all indices 0 to n with all array elements. Pairs cancel, leaving missing number.

Approach: XOR all indices (0 to n) with all array values. Alternative: use Gauss formula n*(n+1)/2 - sum(array).

Complexity: Time O(n), Space O(1)

Number of 1 Bits (LeetCode 191)

Problem: Return the number of set bits (1s) in the binary representation of an integer.

Key Insight: n & (n-1) clears the lowest set bit. Count iterations until n becomes 0.

Approach: While n != 0: increment count and do n = n & (n-1). This is Brian Kernighan's algorithm.

Complexity: Time O(number of set bits), Space O(1)

Find All Numbers Disappeared in an Array (LeetCode 448)

Problem: Array of n integers in range [1, n], some appear twice, some don't. Find all missing numbers.

Key Insight: Use array indices as markers. Negate value at index corresponding to each number seen.

Approach: For each num, mark nums[abs(num)-1] as negative. After marking, indices with positive values are missing.

Complexity: Time O(n), Space O(1) extra

Power of Two (LeetCode 231)

Problem: Determine if n is a power of two.

Key Insight: Powers of two have exactly one set bit. n & (n-1) clears that bit, resulting in 0.

Approach: Return n > 0 and (n & (n-1)) == 0. Must check n > 0 since 0 would pass the bit check.

Complexity: Time O(1), Space O(1)

Medium

Single Number II (LeetCode 137)

Problem: Every element appears three times except one which appears once. Find it.

Key Insight: Count bits at each position mod 3. Bits from the single number remain.

Approach: For each of 32 bit positions, count total set bits across all numbers. If count % 3 != 0, that bit is set in result.

Complexity: Time O(32n) = O(n), Space O(1)

Single Number III (LeetCode 260)

Problem: Exactly two elements appear once, all others appear twice. Find both single elements.

Key Insight: XOR all gives a ^ b. Find any set bit to split numbers into two groups.

Approach: Get xor_all = a ^ b. Find differing bit with xor_all & (-xor_all). Split array by this bit, XOR each group separately.

Complexity: Time O(n), Space O(1)

Find All Duplicates in an Array (LeetCode 442)

Problem: Array of n integers in range [1, n], each appears once or twice. Find all duplicates.

Key Insight: Use sign flipping - negate value at index when number is seen. If already negative, it's a duplicate.

Approach: For each num, check if nums[abs(num)-1] is negative. If yes, add to result. Otherwise negate it.

Complexity: Time O(n), Space O(1) extra

Find the Duplicate Number (LeetCode 287)

Problem: Array of n+1 integers in [1, n] with one duplicate. Find it without modifying array in O(1) space.

Key Insight: Treat as linked list where index i points to nums[i]. Duplicate creates cycle, use Floyd's algorithm.

Approach: Use slow/fast pointers to find cycle, then find cycle entrance which is the duplicate.

Complexity: Time O(n), Space O(1)

Subsets (LeetCode 78)

Problem: Given array of unique elements, return all possible subsets (power set).

Key Insight: Each subset corresponds to a binary number from 0 to 2^n - 1. Bit i indicates whether to include element i.

Approach: For mask from 0 to 2^n - 1: check each bit position, include element if bit is set.

Complexity: Time O(n * 2^n), Space O(n * 2^n) for output

Sum of Two Integers (LeetCode 371)

Problem: Calculate sum of two integers without using + or - operators.

Key Insight: XOR gives sum without carry. AND shifted left gives carry. Repeat until no carry.

Approach: While b != 0: carry = a & b, a = a ^ b, b = carry << 1. Handle negative numbers carefully.

Complexity: Time O(1), Space O(1)

Maximum XOR of Two Numbers in Array (LeetCode 421)

Problem: Find maximum XOR of two elements in an array.

Key Insight: Build answer bit by bit from MSB. Use Trie or set to check if higher bit can be set.

Approach: For each bit position from high to low, try to set it in result. Use prefix set to verify achievability.

Complexity: Time O(32n), Space O(n)

Hard

First Missing Positive (LeetCode 41)

Problem: Find the smallest missing positive integer. Must run in O(n) time and O(1) space.

Key Insight: Answer must be in [1, n+1]. Use cyclic sort to place each number at its correct index.

Approach: Place num at index num-1 using swaps. Then scan for first index where nums[i] != i+1. That's the answer.

Complexity: Time O(n), Space O(1)

Maximum AND Sum of Array (LeetCode 2172)

Problem: Distribute array elements into numSlots slots (each slot holds at most 2 elements). Maximize sum of (slot_number AND element).

Key Insight: Use bitmask DP where state encodes slot assignments.

Approach: DP with bitmask representing which slot positions are filled. Transition by assigning current element to each valid slot.

Complexity: Time O(n * 3^numSlots), Space O(3^numSlots)

Quick Reference Card

Bit Manipulation Cheat Sheet

python

# Check bit i
(n >> i) & 1        # or: n & (1 << i)

# Set bit i
n | (1 << i)

# Clear bit i
n & ~(1 << i)

# Toggle bit i
n ^ (1 << i)

# Clear lowest set bit
n & (n - 1)

# Isolate lowest set bit
n & (-n)

# Check power of 2
n > 0 and n & (n - 1) == 0

# Count set bits
bin(n).count('1')   # Python built-in

Cyclic Sort Template

PythonJava

python

i = 0
while i < len(nums):
    correct = nums[i] - 1  # Adjust for 0-indexed: correct = nums[i]
    if nums[i] != nums[correct]:
        nums[i], nums[correct] = nums[correct], nums[i]
    else:
        i += 1

java

int i = 0;
while (i < nums.length) {
    int correct = nums[i] - 1; // for 0-indexed: correct = nums[i]
    if (nums[i] != nums[correct]) {
        int tmp = nums[i]; nums[i] = nums[correct]; nums[correct] = tmp;
    } else {
        i++;
    }
}

Bit Manipulation & Cyclic Sort Patterns ​

Bit Manipulation Pattern ​

Why Bit Manipulation Matters ​

Core Bitwise Operators ​

Essential Bit Operations ​

XOR Properties ​

Template Code ​

Classic Problems ​

Cyclic Sort Pattern ​

Concept ​

When to Use Cyclic Sort ​

Algorithm Characteristics ​

Template Code ​

Classic Problems ​

Visual Example: Cyclic Sort Process ​

Interview Applications ​

Bit Manipulation in Interviews ​

Cyclic Sort in Interviews ​

Interview Tips ​

Complexity Comparison ​

Practice Problems by Difficulty ​

Easy ​

Medium ​

Hard ​

Quick Reference Card ​

Bit Manipulation Cheat Sheet ​

Cyclic Sort Template ​

References ​

Bit Manipulation & Cyclic Sort Patterns

Bit Manipulation Pattern

Why Bit Manipulation Matters

Core Bitwise Operators

Essential Bit Operations

XOR Properties

Template Code

Classic Problems

Cyclic Sort Pattern

Concept

When to Use Cyclic Sort

Algorithm Characteristics

Template Code

Classic Problems

Visual Example: Cyclic Sort Process

Interview Applications

Bit Manipulation in Interviews

Cyclic Sort in Interviews

Interview Tips

Complexity Comparison

Practice Problems by Difficulty

Easy

Medium

Hard

Quick Reference Card

Bit Manipulation Cheat Sheet

Cyclic Sort Template

References