webcoderspeed.com
26 articles
Find the element that appears once while every other appears twice. The XOR bit trick gives O(n) time and O(1) space. Full solutions in C, C++, Java, JavaScript, Python plus Single Number II and III extensions.
Find the missing number in [0,n]. Two elegant O(n) O(1) solutions: Gauss formula and XOR trick. Full solutions in C, C++, Java, JavaScript and Python.
Generate the power set of distinct integers using backtracking or bitmask enumeration.
Find the missing number in [0..n] using the Gauss sum formula or XOR in O(n) time O(1) space.
Find the single non-duplicate element in O(log n) by observing that pairs shift the parity of indices after the singleton.
Master bit manipulation: XOR tricks, counting bits, bitmask DP, Brian Kernighan, two's complement, and 5-language operators.
Every element appears twice except one. XOR all numbers: duplicates cancel (a^a=0), single number remains.
Every element appears 3 times except one. Track bit counts mod 3: ones and twos bitmasks, or count each bit position.
Two numbers appear once, rest appear twice. XOR all to get a^b, then use any set bit to partition numbers into two groups.
Count set bits (popcount). Brian Kernighan: n & (n-1) clears the lowest set bit; count how many operations until n=0.
Count set bits for all numbers 0..n. DP: dp[i] = dp[i >> 1] + (i & 1). Remove last bit and check if it was set.
Reverse bits of a 32-bit unsigned integer. Shift result left and input right 32 times, taking last bit each time.
Find missing number in 0..n array. XOR approach: XOR all indices with all values, duplicate indices cancel. Or math: n*(n+1)/2 - sum.
Add two integers without + or - operators. Simulate: sum = a XOR b (no carry), carry = (a AND b) << 1. Repeat until carry = 0.
Generate all subsets of an array. Each subset corresponds to a bitmask of n bits where bit i = 1 means element i is included.
Can array be partitioned into k equal-sum subsets? Bitmask DP: dp[mask] = sum filled so far. O(2^n * n) instead of O(k^n) DFS.
Sum of Hamming distances between all pairs. For each bit position, count 0s and 1s: contribution = count_0 * count_1.
AND of all numbers in [left, right]. Result is the common prefix of left and right: keep shifting right until equal, then shift back.
Assign each element of nums1 to exactly one element of nums2 to minimize XOR sum. Classic assignment bitmask DP: dp[mask] = min XOR sum.
Generate n-bit Gray code sequence where adjacent codes differ by exactly 1 bit. Formula: gray(i) = i ^ (i >> 1).
Find all 10-letter DNA sequences that appear more than once. Use rolling hash (4-bit per char) or set of seen substrings.
Count words that contain puzzle[0] and only letters from puzzle. Encode words as bitmasks, for each puzzle enumerate its subsets containing puzzle[0].
Find max product of lengths of two words with no common letters. Encode each word as bitmask; two words share letters if AND != 0.
Complete bit manipulation cheatsheet: all critical tricks, bitmask DP patterns, XOR properties, complexity table, and problem index.
Count pairs summing to a power of 2 by checking all 22 powers-of-2 against a running frequency map.
Convert a linked list representing a binary number to its integer value using left-shift accumulation.