#1009

Easy

auto_awesomeBit Manipulation-driven solution strategy

LeetCode Problem Workspace

Complement of Base 10 Integer

In this problem, you need to return the complement of a given integer by flipping its binary digits.

Problem Statement

The complement of an integer is derived by flipping all the bits in its binary representation, changing 1's to 0's and 0's to 1's.

Given an integer n, you are tasked with returning its complement, where the complement is calculated by flipping each bit in its binary form.

Examples

Example 1

Input: n = 5

Output: 2

5 is "101" in binary, with complement "010" in binary, which is 2 in base-10.

Example 2

Input: n = 7

Output: 0

7 is "111" in binary, with complement "000" in binary, which is 0 in base-10.

Example 3

Input: n = 10

Output: 5

10 is "1010" in binary, with complement "0101" in binary, which is 5 in base-10.

Constraints

0 <= n < 109

Solution Approach

Bitwise XOR approach

One efficient way to compute the complement is by using the XOR operation. First, calculate a mask where all bits are 1 for the number of bits in n. Then XOR the number with the mask, flipping all bits to produce the complement.

Inverting bits with subtraction

Another approach involves subtracting n from a number that consists entirely of 1's, which has the same bit-length as n. This subtraction inverts the bits of n, effectively providing the complement.

Handling edge cases

In cases where n equals 0, the complement is simply 1. This corner case needs special handling to ensure the solution accounts for it.

Complexity Analysis

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

The time complexity of the solution depends on the number of bits in the integer n, which is O(log n). The space complexity is O(1), as the approach uses a constant amount of extra space.

What Interviewers Usually Probe

Look for knowledge of bitwise operations and how they are used to manipulate binary representations.
Assess understanding of how to handle edge cases such as when n is 0.
Evaluate familiarity with time and space complexities related to bit manipulation problems.

Common Pitfalls or Variants

Common pitfalls

Failing to account for the edge case where n equals 0, which should return 1.
Incorrectly handling large values of n by not properly calculating the bit-length.
Overcomplicating the problem by trying unnecessary operations rather than using simple bitwise manipulation.

Follow-up variants

What if the complement is computed for a list of integers instead of a single value?
Can the solution be optimized for extremely large values of n, such as those near 10^9?
How can you apply this bitwise technique to other problems involving binary operations?

FAQ

How do you solve the 'Complement of Base 10 Integer' problem?

To solve this problem, use bitwise operations such as XOR to flip the binary digits of the given integer and return its complement.

What is the time complexity of the complement problem?

The time complexity is O(log n), as it depends on the number of bits in the integer n.

What is the space complexity for the complement problem?

The space complexity is O(1) because the solution uses a constant amount of extra space.

How should you handle edge cases in the complement problem?

When n equals 0, return 1 as its complement. Ensure to handle this edge case properly.

What is the pattern in the 'Complement of Base 10 Integer' problem?

The problem follows a bit manipulation pattern where the complement is computed by flipping the binary digits of an integer using bitwise operations.

terminal

Solution

Solution 1: Bit Manipulation

First, we check if $n$ is $0$. If it is, we return $1$.

1

2

3

4

5

6

7

8

9

10

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

Continue Practicing

#1016 binary string with substrings representing 1 to n #1018 binary prefix divisible by 5 #996 number of squareful arrays