Complement of Base 10 Integer — Easy Problem & Solution

Problem statement

The complement of a number flips every bit of its binary representation, ignoring leading zeros. The complement of 5 (binary 101) is 2 (binary 010).

Given a non-negative integer n, return its complement.

Example 1

Input: n = 5
Output: 2
Explanation: 101 flips to 010.

Example 2

Input: n = 7
Output: 0
Explanation: 111 flips to 000.

Example 3

Input: n = 0
Output: 1
Explanation: 0 is written as the single bit 0, which flips to 1.

Constraints

• 0 <= n < 1000000000

How to solve Complement of Base 10 Integer

Flipping every bit of an L-bit number is the same as subtracting it from the L-bit all-ones value, because each bit position independently goes from b to 1 - b.

Approach

1. Handle n == 0 separately, returning 1.
2. Find the smallest power of two strictly greater than n; call it mask.
3. Return mask - 1 - n, since mask - 1 is the all-ones value of the right width.

Why it works

If n has L significant bits then mask - 1 = 2^L - 1 is exactly L ones, and (2^L - 1) - n flips each of those bits. Ignoring leading zeros is precisely what choosing L from n itself achieves.

Complexity

• Time — O(log n)
• Space — O(1)

Pitfalls

• Using ~n flips the full machine word and yields a negative number.
• n = 0 has no set bits, so the mask loop must be guarded or it returns 0 instead of 1.
• In JavaScript, doubling past 2^31 stays exact as a double, but 1 << 31 would go negative.

Reference solution

Python

def bitwiseComplement(n: int) -> int:
    if n == 0:
        return 1
    mask = 1
    while mask <= n:
        mask <<= 1
    return mask - 1 - n

JavaScript

var bitwiseComplement = function(n) {
    if (n === 0) return 1;
    var mask = 1;
    while (mask <= n) mask *= 2;
    return mask - 1 - n;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Number of Bit Changes to Make Two Integers Equal Easy
• Find the XOR of Numbers Which Appear Twice Easy
• Binary Watch Easy
• Smallest Number With All Set Bits Easy
• Shortest Subarray With OR at Least K I Easy
• Maximum Strong Pair XOR I Easy