Complement of Base 10 Integer

Easy
720.

Complement of Base 10 Integer

Complement of Base 10 Integer is an easy coding problem on math and bit manipulation, asked in TCS, Wipro and Accenture interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var bitwiseComplement = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Complement of Base 10 Integer — Problem & Solution

Complement of Base 10 Integer solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Complement of Base 10 Integer is an easy coding problem on math and bit manipulation, asked in TCS, Wipro and Accenture interviews.

  • Difficulty: Easy
  • Topics: Math, Bit Manipulation
  • Asked at: TCS, Wipro, Accenture
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Complement of Base 10 Integer

  1. Hint 1

    Build the all-ones mask with the same number of bits as n.

  2. Hint 2

    Then the complement is mask - n, since mask has a 1 wherever n has a bit position at all.

  3. Hint 3

    n = 0 is the special case — its complement is 1.

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

Java

public static int bitwiseComplement(int n) {
    if (n == 0) return 1;
    long mask = 1;
    while (mask <= n) mask <<= 1;
    return (int) (mask - 1 - n);
}

C++

int bitwiseComplement(int n) {
    if (n == 0) return 1;
    long long mask = 1;
    while (mask <= n) mask <<= 1;
    return (int) (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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Bit Manipulation