Number Complement

Easy
417.

Number Complement

Number Complement is an easy coding problem on bit manipulation, asked in Amazon, Adobe and Apple interviews.

The complement of an integer is what you get by flipping every bit in its binary representation, without any leading zeros.

Given a positive integer num, return its complement.

Example 1

Input
num = 5
Output
2
Explanation
101 flips to 010, which is 2.

Example 2

Input
num = 1
Output
0

Example 3

Input
num = 7
Output
0

Constraints

  • 1 <= num <= 2147483646
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} num
 * @return {number}
 */
var findComplement = function(num) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number Complement — Solution in Python, Java & C++

Number Complement solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on bit manipulation.

Number Complement is an easy coding problem on bit manipulation, asked in Amazon, Adobe and Apple interviews.

  • Difficulty: Easy
  • Topics: Bit Manipulation
  • Asked at: Amazon, Adobe, Apple
  • 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 an integer is what you get by flipping every bit in its binary representation, without any leading zeros.

Given a positive integer num, return its complement.

Example 1

Input: num = 5
Output: 2
Explanation: 101 flips to 010, which is 2.

Example 2

Input: num = 1
Output: 0

Example 3

Input: num = 7
Output: 0

Constraints

  • 1 <= num <= 2147483646

Hints for Number Complement

  1. Hint 1

    The trick is not flipping the 32 bits — it is knowing where to stop.

  2. Hint 2

    Build a mask of all 1s that is exactly as wide as num's binary representation.

  3. Hint 3

    Then the answer is mask ^ num.

How to solve Number Complement

Build a mask of ones exactly as wide as num, then XOR.

Approach

  1. Shift mask left inserting ones while a copy of num is non-zero.
  2. Return mask ^ num.

Why it works

XOR with all-ones flips every bit; limiting the mask's width keeps leading zeros from becoming ones.

Complexity

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

Pitfalls

  • Flipping all 32 bits gives the wrong answer for anything below 2³¹.

Reference solution

Python

def findComplement(num: int) -> int:
    mask = 0
    v = num
    while v:
        mask = (mask << 1) | 1
        v >>= 1
    return mask ^ num

Java

public static int findComplement(int num) {
    long mask = 0;
    long v = num;
    while (v > 0) {
        mask = mask * 2 + 1;
        v /= 2;
    }
    return (int) (mask - num);
}

C++

int findComplement(int num) {
    long long mask = 0;
    long long v = num;
    while (v > 0) {
        mask = mask * 2 + 1;
        v /= 2;
    }
    return (int) (mask - num);
}

JavaScript

var findComplement = function(num) {
    let mask = 0;
    let v = num;
    while (v > 0) {
        mask = (mask << 1) | 1;
        v = Math.floor(v / 2);
    }
    return (mask ^ num) >>> 0;
};

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

All 146 bit manipulation problems · the whole catalogue

Learn the technique: Bit Manipulation