How do you solve Number Complement on LeetCode?

Number Complement (LeetCode #476) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(1) time complexity and O(1) space complexity. Key insight: Understanding bit manipulation can lead to more efficient solutions.

What is the brute force solution for Number Complement?

The brute force approach for Number Complement is Brute Force, with O(n²) time complexity and O(n) space complexity. The brute force approach involves converting the number to its binary representation, flipping each bit, and then converting it back to a decimal integer. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(1).

What algorithm or data structure is used to solve Number Complement?

Number Complement uses the following concepts: Bit Manipulation. The recommended patterns to study are: Bit Manipulation.

What are the interview tips for Number Complement?

Always clarify the constraints and edge cases before diving into coding. Explain your thought process as you code; this helps interviewers follow your logic. Practice bit manipulation problems to become comfortable with the concepts.

What are common mistakes when solving Number Complement?

Confusing binary representation with decimal values during conversion. Not considering edge cases like the smallest input.

#476

Number Complement

Easy

Bit ManipulationBit Manipulation

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(1)
Space	O(n)	O(1)

💡

Intuition

Time O(1)Space O(1)

The optimal approach leverages bit manipulation to find the complement without converting to binary strings. This is efficient and operates directly on the integer's bits.

⚙️

Algorithm

2 steps

1Step 1: Create a mask with all bits set to 1 that are relevant to the number.
2Step 2: XOR the number with the mask to flip the bits.

solution.py5 lines

1# Full working Python code
2
3def findComplement(num):
4    mask = (1 << num.bit_length()) - 1
5    return num ^ mask

ℹ

Complexity note: The time complexity is O(1) since we perform a constant number of operations regardless of the input size. The space complexity is also O(1) as we only use a few variables.

1Understanding bit manipulation can lead to more efficient solutions.
2Using XOR is a powerful technique for flipping bits.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.