O(1) low-level bitwise operations, masks, and XOR parity tricks
Perform bitwise operations (&, |, ^, ~, <<, >>) to check, set, toggle, or count bits in O(1) time and space without allocating memory.
Core Invariant: Essential Bit Identities: 1) `x ^ x = 0` and `x ^ 0 = x` (cancels pairs); 2) `n & (n - 1)` clears the lowest set bit (Brian Kernighan); 3) `n & -n` isolates lowest set bit; 4) `(1 << k)` creates mask for k-th bit.
Numbers exceed 64-bit integer limits and bitwise representations become complex strings, or problem requires decimal digits.
def single_number(nums: list[int]) -> int:
# XOR Property: x ^ x = 0 and x ^ 0 = x
# All duplicate pairs cancel out, leaving the unique single number
unique = 0
for x in nums:
unique ^= x
return unique
def count_set_bits(n: int) -> int:
# Brian Kernighan's Algorithm: n & (n - 1) clears the lowest set bit
count = 0
while n > 0:
n &= (n - 1)
count += 1
return count# | Problem | Difficulty | Top Companies↓ | Frequency | Acceptance | |
|---|---|---|---|---|---|---|
| #78 | Subsets ArrayBacktrackingBit Manipulation | Medium | 100% | 0.8% | ||
| #287 | Find the Duplicate Number ArrayTwo PointersBinary SearchBit ManipulationPigeonhole PrincipleFloyd's Cycle Finding Algorithm | Medium | 90% | 64.6% | ||
| #268 | Missing Number ArrayHash TableMathBinary SearchBit ManipulationSorting | Easy | 84% | 72.3% | ||
| #136 | Single Number ArrayBit Manipulation | Easy | 75% | 77.9% | ||
| #67 | Add Binary MathStringBit ManipulationSimulation | Easy | 63% | 58.3% | ||
| #465 | Optimal Account Balancing ArrayDynamic ProgrammingBacktrackingBit ManipulationBitmask | Hard | 100% | 50.5% | ||
| #191 | Number of 1 Bits Divide and ConquerBit Manipulation | Easy | 89% | 77.1% | ||
| #190 | Reverse Bits Divide and ConquerBit Manipulation | Easy | 76% | 68.8% | ||
| #231 | Power of Two MathBit ManipulationRecursion | Easy | 76% | 50.3% | ||
| #338 | Counting Bits Dynamic ProgrammingBit Manipulation | Easy | 58% | 0.8% | ||
| #371 | Sum of Two Integers MathBit Manipulation | Medium | 100% | 55.8% | ||
| #90 | Subsets II ArrayBacktrackingBit Manipulation | Medium | 79% | 61.6% | ||
| #2035 | Partition Array Into Two Arrays to Minimize Sum Difference ArrayTwo PointersBinary SearchDynamic ProgrammingBit ManipulationMeet in the MiddleSortingOrdered SetBitmask | Hard | 100% | 23.9% | ||
| #473 | Matchsticks to Square ArrayDynamic ProgrammingBacktrackingBit ManipulationBitmask | Medium | 100% | 42.1% | ||
| #2571 | Minimum Operations to Reduce an Integer to 0 Dynamic ProgrammingGreedyBit Manipulation | Medium | 100% | 62.8% | ||
| #1386 | Cinema Seat Allocation ArrayHash TableGreedyBit Manipulation | Medium | 97% | 44.7% | ||
| #1404 | Number of Steps to Reduce a Number in Binary Representation to One StringBit ManipulationSimulation | Medium | 93% | 63.7% | ||
| #698 | Partition to K Equal Sum Subsets ArrayDynamic ProgrammingBacktrackingBit ManipulationMemoizationBitmask | Medium | 75% | 38.8% | ||
| #29 | Divide Two Integers MathBit Manipulation | Medium | 75% | 20.0% | ||
| #2850 | Minimum Moves to Spread Stones Over Grid ArrayDynamic ProgrammingBacktrackingBit ManipulationMatrixBitmask | Medium | 100% | 45.9% | ||
| #868 | Binary Gap Bit Manipulation | Easy | 100% | 0.7% | ||
| #864 | Shortest Path to Get All Keys ArrayBit ManipulationBreadth-First SearchMatrix | Hard | 100% | 54.8% | ||
| #2220 | Minimum Bit Flips to Convert Number Bit Manipulation | Easy | 100% | 88.0% | ||
| #784 | Letter Case Permutation StringBacktrackingBit Manipulation | Medium | 100% | 75.9% | ||
| #1342 | Number of Steps to Reduce a Number to Zero MathBit Manipulation | Easy | 100% | 85.9% | ||
| #187 | Repeated DNA Sequences Hash TableStringBit ManipulationSliding WindowRolling HashHash FunctionZ AlgorithmBoyer–Moore String-Search Algorithm | Medium | 88% | 53.6% | ||
| #898 | Bitwise ORs of Subarrays ArrayDynamic ProgrammingBit Manipulation | Medium | 75% | 56.9% | ||
| #222 | Count Complete Tree Nodes Binary SearchBit ManipulationTreeBinary Tree | Medium | 68% | 73.1% | ||
| #526 | Beautiful Arrangement ArrayDynamic ProgrammingBacktrackingBit ManipulationBitmask | Medium | 66% | 0.7% | ||
| #260 | Single Number III ArrayBit Manipulation | Medium | 65% | 70.2% | ||
| #2044 | Count Number of Maximum Bitwise-OR Subsets ArrayBacktrackingBit ManipulationEnumeration | Medium | 65% | 89.5% | ||
| #779 | K-th Symbol in Grammar MathBit ManipulationRecursion | Medium | 63% | 48.5% | ||
| #980 | Unique Paths III ArrayBacktrackingBit ManipulationMatrixHamiltonian Path | Hard | 54% | 82.9% | ||
| #2791 | Count Paths That Can Form a Palindrome in a Tree Hash TableBit ManipulationTreeDepth-First Search | Hard | 100% | 52.7% | ||
| #2401 | Longest Nice Subarray ArrayBit ManipulationSliding Window | Medium | 100% | 64.8% | ||
| #3011 | Find if Array Can Be Sorted ArrayBit ManipulationSorting | Medium | 100% | 66.4% | ||
| #2419 | Longest Subarray With Maximum Bitwise AND ArrayBit ManipulationBrainteaser | Medium | 100% | 65.4% | ||
| #638 | Shopping Offers ArrayDynamic ProgrammingBacktrackingBit ManipulationMemoizationBitmaskKnapsack ProblemComplete Knapsack | Medium | 96% | 52.6% | ||
| #1611 | Minimum One Bit Operations to Make Integers Zero MathDynamic ProgrammingBit ManipulationRecursionMemoization | Hard | 91% | 78.3% | ||
| #2429 | Minimize XOR GreedyBit Manipulation | Medium | 88% | 62.4% | ||
| #3108 | Minimum Cost Walk in Weighted Graph ArrayBit ManipulationUnion-FindGraph Theory | Hard | 75% | 68.2% | ||
| #2438 | Range Product Queries of Powers ArrayBit ManipulationPrefix Sum | Medium | 68% | 61.2% | ||
| #2657 | Find the Prefix Common Array of Two Arrays ArrayHash TableBit Manipulation | Medium | 67% | 88.3% | ||
| #805 | Split Array With Same Average ArrayHash TableMathDynamic ProgrammingBit ManipulationMeet in the MiddleBitmask | Hard | 67% | 27.2% | ||
| #3191 | Minimum Operations to Make Binary Array Elements Equal to One I ArrayBit ManipulationQueueSliding WindowPrefix Sum | Medium | 50% | 80.4% | ||
| #389 | Find the Difference Hash TableStringBit ManipulationSorting | Easy | 44% | 60.5% | ||
| #832 | Flipping an Image ArrayTwo PointersBit ManipulationMatrixSimulation | Easy | 42% | 83.9% | ||
| #1930 | Unique Length-3 Palindromic Subsequences Hash TableStringBit ManipulationPrefix Sum | Medium | 39% | 73.8% | ||
| #1371 | Find the Longest Substring Containing Vowels in Even Counts Hash TableStringBit ManipulationPrefix Sum | Medium | 38% | 75.6% | ||
| #2939 | Maximum Xor Product MathGreedyBit Manipulation | Medium | 100% | 30.2% |
Browse company-specific interview problem lists and recency breakdowns:
Master core algorithmic patterns tested in FAANG & Big Tech coding interviews.
O(1) low-level bitwise operations, masks, and XOR parity tricks It is categorized under Advanced & DP and features 238 curated interview problems across Easy (45), Medium (110), and Hard (83) difficulties.
Companies frequently asking Bit Manipulation questions include Google, Amazon, Microsoft, Meta, Bloomberg, NeetCode 150.
Start by studying the algorithmic strategy and template code, then practice Easy and Medium problems before attempting Hard problems under timed conditions.