1009. Complement of Base 10 Integer
Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 0
Acceptance rate: 61.4%
Problem Breakdown
The problem requires finding the complement of a given non-negative integer N in its binary representation. The complement is obtained by flipping all bits in the binary form of N. For example:
- Input: 5 (binary “101”) -> Output: 2 (binary “010”)
- Input: 7 (binary “111”) -> Output: 0 (binary “000”)
- Input: 10 (binary “1010”) -> Output: 5 (binary “0101”)
Inputs: A non-negative integer N where 0 <= N < 10^9.
Outputs: The complement of the binary representation of N, returned as a base-10 integer.
Implicit Constraints:
- No leading zeroes in binary representations except for
N = 0. - Edge cases include
N = 0and powers of two, which have all bits set to zero except one.
Intuition
A brute-force approach would involve converting the number to a binary string, flipping each bit, and then converting it back to an integer. However, this method is inefficient due to multiple conversions and manipulations of strings.
The key insight is that the complement of N can be found by XORing N with a mask that has all bits set to 1 up to the highest bit in N. This avoids string manipulation and leverages bitwise operations for efficiency.
Approach
- Edge Case Handling: If
Nis 0, return 1 directly since its complement is “1”. - Determine Mask Length: Calculate the number of bits required to represent
Nin binary. - Create Mask: Generate a mask with all bits set to 1 up to the highest bit position found in step 2.
- Compute Complement: XOR
Nwith the mask to get its complement.
Complexity Analysis
- Time Complexity: O(log N) due to the loop that calculates the number of bits required for
N. - Space Complexity: O(1) as we are using a constant amount of extra space regardless of input size.
Solution
def bitwiseComplement(N: int) -> int:
if N == 0:
return 1
# Determine the number of bits in N
num_bits = 0
temp = N
while temp > 0:
temp >>= 1
num_bits += 1
# Create a mask with all bits set to 1 up to num_bits
mask = (1 << num_bits) - 1
# Compute the complement by XORing N with the mask
return N ^ mask
Edge Cases Handled
- N = 0: The code directly returns 1, as the binary representation of 0 is “0”, and its complement is “1”.
- Powers of Two: For numbers like 2 (binary “10”), 4 (binary “100”), etc., the mask will have all bits set to 1 up to the highest bit position, resulting in a complement that flips only the highest bit.
- General Case: The approach works for any non-negative integer within the given constraints by flipping all bits in its binary representation.