XOR for toggle/cancel, AND for masking, shifts for multiply/divide by 2. Bit tricks are elegant but require knowing specific properties of binary operations.
Problems: 7
Easy: 5
Medium: 2
Hard: 0
Learning approach: Read the problem. Try the test cases yourself first.
Click Hint if stuck — it guides without spoiling.
Use Show Solution only after a genuine attempt.
Then hit Let's Code to run your solution live.
XOR all numbers. Pairs cancel out (a^a=0). What's left is the single number.
Python Solution
def singleNumber(nums):
result = 0
for n in nums:
result ^= n # pairs cancel, single remains
return result
Key idea: XOR has two key properties: a ^ a = 0 (same number cancels) and a ^ 0 = a (identity). XOR-ing all numbers cancels all pairs, leaving only the unique element.
n & (n-1) clears LSBO(k) k=set bitsBrian Kernighan
The trick n & (n-1) clears the lowest set bit. Count how many times you can do this before n becomes 0.
Python Solution
def hammingWeight(n):
count = 0
while n:
n &= n - 1 # clear the lowest set bit
count += 1
return count
Key idea: Brian Kernighan's trick: n & (n-1) always clears the rightmost set bit. Count iterations until n becomes 0. This runs in O(k) where k is the number of set bits.
Time: O(k) where k = number of 1-bits. Space: O(1).
XOR gives sum bits (without carry). AND gives carry bits — shift them left by 1. Repeat until carry is zero. Use a 32-bit mask for Python.
Python Solution
def getSum(a, b):
mask = 0xFFFFFFFF
while b & mask:
a, b = (a ^ b) & mask, ((a & b) << 1) & mask
# Convert from 32-bit unsigned to Python signed int
if a > 0x7FFFFFFF:
a = ~(a ^ mask)
return a
Key idea: a ^ b gives the sum bits without carry. (a & b) << 1 gives the carry bits. Repeat until no carry. The mask handles Python's arbitrary precision int by constraining to 32 bits.