#476

Easy

auto_awesomeBit Manipulation-driven solution strategy

LeetCode Problem Workspace

Number Complement

The Number Complement problem requires flipping bits in a number’s binary representation to return its complement.

Problem Statement

Given an integer num, you are tasked with returning its complement. The complement is derived by flipping all the bits in its binary representation, turning 0’s to 1’s and 1’s to 0’s. No leading zero bits are involved, and the result must maintain the size of the binary representation of num.

For example, if num = 5, its binary representation is 101, and flipping each bit results in 010, which is the binary representation of 2. This challenge tests your ability to use bit manipulation to efficiently compute the complement of a number.

Examples

Example 1

Input: num = 5

Output: 2

The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

Example 2

Input: num = 1

Output: 0

The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

Constraints

1 <= num < 231

Solution Approach

Bitwise XOR Solution

You can find the complement of a number by using the XOR operation with a number that has all bits set to 1. The XOR between num and this mask will flip all its bits and give the complement.

Bit Length Strategy

To create the mask, you need to identify the number of bits in num and generate a mask where all the bits are 1. The complement is then calculated by XOR-ing the mask with num.

Optimized Approach

Instead of directly calculating the mask, you can perform operations to determine the flipped bits more efficiently by calculating the complement using arithmetic operations to avoid creating large masks.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the number of bits in the binary representation of the number. In the worst case, this is proportional to the log of the number, i.e., O(log(num)). Space complexity can be constant O(1), as the approach only requires a few variables for the operation.

What Interviewers Usually Probe

Ability to apply bitwise operations effectively.
Understanding of binary number representations and manipulation.
Ability to explain optimization of bit manipulation techniques.

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle edge cases like when num is a single bit (i.e., 1 or 0).
Confusing the number of bits with the actual value of the complement.
Overcomplicating the solution instead of focusing on simple bitwise operations.

Follow-up variants

Can you find a way to solve this problem using just arithmetic?
What if you were limited by space constraints and could only use a fixed number of variables?
Can you modify this solution to work with negative integers?

FAQ

What is the Number Complement problem?

The Number Complement problem asks you to flip all bits in the binary representation of an integer and return its complement.

How do you approach the Number Complement problem?

You can solve it by generating a mask with all 1’s and XOR-ing it with the original number. Alternatively, you can calculate the complement by flipping the bits based on the binary length.

What bit manipulation operations are useful for solving the Number Complement problem?

XOR is the primary operation used, as it effectively flips the bits when applied to a mask of 1’s.

Can the Number Complement problem be optimized further?

Yes, using more efficient methods to generate the mask or simplifying the solution using arithmetic tricks can improve performance.

How does the problem's pattern apply to other bit manipulation challenges?

The Number Complement problem demonstrates how bit manipulation can be used to flip specific bits, which is a common technique in problems involving binary representations or toggling states.

terminal

Solution

Solution 1: Bit Manipulation

According to the problem description, we can use XOR operation to implement the flipping operation, the steps are as follows:

1

2

3

class Solution:
    def findComplement(self, num: int) -> int:
        return num ^ ((1 << num.bit_length()) - 1)

Solution 2: Bit Manipulation. Inversion + AND

#### TypeScript

1

2

3

class Solution:
    def findComplement(self, num: int) -> int:
        return num ^ ((1 << num.bit_length()) - 1)

Continue Practicing

#477 total hamming distance #473 matchsticks to square #464 can i win