Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Build confidence with an intuition-first walkthrough focused on bit manipulation fundamentals.
The complement of an integer is the integer you get when you flip all the 0's to 1's and all the 1's to 0's in its binary representation.
5 is "101" in binary and its complement is "010" which is the integer 2.Given an integer n, return its complement.
Example 1:
Input: n = 5 Output: 2 Explanation: 5 is "101" in binary, with complement "010" in binary, which is 2 in base-10.
Example 2:
Input: n = 7 Output: 0 Explanation: 7 is "111" in binary, with complement "000" in binary, which is 0 in base-10.
Example 3:
Input: n = 10 Output: 5 Explanation: 10 is "1010" in binary, with complement "0101" in binary, which is 5 in base-10.
Constraints:
0 <= n < 109Note: This question is the same as 476: https://leetcode.com/problems/number-complement/
Problem summary: The complement of an integer is the integer you get when you flip all the 0's to 1's and all the 1's to 0's in its binary representation. For example, The integer 5 is "101" in binary and its complement is "010" which is the integer 2. Given an integer n, return its complement.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Bit Manipulation
5
7
10
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1009: Complement of Base 10 Integer
class Solution {
public int bitwiseComplement(int n) {
if (n == 0) {
return 1;
}
int ans = 0, i = 0;
while (n != 0) {
ans |= (n & 1 ^ 1) << (i++);
n >>= 1;
}
return ans;
}
}
// Accepted solution for LeetCode #1009: Complement of Base 10 Integer
func bitwiseComplement(n int) (ans int) {
if n == 0 {
return 1
}
for i := 0; n != 0; n >>= 1 {
ans |= (n&1 ^ 1) << i
i++
}
return
}
# Accepted solution for LeetCode #1009: Complement of Base 10 Integer
class Solution:
def bitwiseComplement(self, n: int) -> int:
if n == 0:
return 1
ans = i = 0
while n:
ans |= (n & 1 ^ 1) << i
i += 1
n >>= 1
return ans
// Accepted solution for LeetCode #1009: Complement of Base 10 Integer
impl Solution {
pub fn bitwise_complement(mut n: i32) -> i32 {
if n == 0 {
return 1;
}
let mut ans = 0;
let mut i = 0;
while n != 0 {
ans |= ((n & 1) ^ 1) << i;
n >>= 1;
i += 1;
}
ans
}
}
// Accepted solution for LeetCode #1009: Complement of Base 10 Integer
function bitwiseComplement(n: number): number {
if (n === 0) {
return 1;
}
let ans = 0;
for (let i = 0; n; n >>= 1) {
ans |= ((n & 1) ^ 1) << i++;
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Sort the array in O(n log n), then scan for the missing or unique element by comparing adjacent pairs. Sorting requires O(n) auxiliary space (or O(1) with in-place sort but O(n log n) time remains). The sort step dominates.
Bitwise operations (AND, OR, XOR, shifts) are O(1) per operation on fixed-width integers. A single pass through the input with bit operations gives O(n) time. The key insight: XOR of a number with itself is 0, which eliminates duplicates without extra space.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.