476. Number Complement
Model: qwen2.5-coder:14b
Topics: Bit Manipulation
FAANG asked: 1
Acceptance rate: 65.2%
Problem Breakdown
The problem requires finding the complement of a given positive integer num. The complement is obtained by flipping all the bits in its binary representation. For example, if the binary representation of num is 101, its complement would be 010.
Inputs:
- A positive integer
num
Outputs:
- An integer representing the bit-wise complement of
num
Implicit Constraints:
- The input
numfits within a 32-bit signed integer range. - There are no leading zero bits in the binary representation of
num.
Intuition
A brute-force approach would involve converting the number to its binary form, flipping each bit manually, and then converting it back to an integer. However, this method is inefficient in terms of both time and space complexity.
The key insight is to use bitwise operations to efficiently flip all bits. Specifically, we can XOR num with a mask that has the same number of bits as num, where each bit in the mask is set to 1. This operation will flip all bits in num.
Approach
- Determine the Bit Length: Calculate the number of bits required to represent
numusinglog2(num) + 1. - Create a Mask: Generate a mask with all bits set to 1 that has the same length as the bit representation of
num. This can be done by shifting 1 left by the bit length and then subtracting 1. - Compute the Complement: Use the XOR operation between
numand the mask to flip all bits.
Complexity Analysis
- Time Complexity: O(log(num)), where log is base 2, due to the calculation of the bit length.
- Space Complexity: O(1), as we are using a constant amount of extra space.
Solution
def findComplement(num: int) -> int:
# Determine the number of bits in num
bit_length = num.bit_length()
# Create a mask with all bits set to 1 that has the same length as num
mask = (1 << bit_length) - 1
# Compute and return the complement using XOR
return num ^ mask
Edge Cases Handled
- Single Bit Number: If
numis 1, its binary representation is1, and the complement should be0. - Power of Two: For numbers like 4 (
100in binary), the complement will be011which is 3. - Max 32-bit Integer: The solution handles the maximum 32-bit integer by ensuring the mask correctly covers all bits.
This approach ensures that we efficiently compute the bit-wise complement with optimal time and space complexity.