476. Number Complement - Solution & Explanation

Q: Is Number Complement easy or hard?

Number Complement is classified as an Easy problem on LeetCode. The challenge mainly tests basic understanding of binary numbers, bit masks, and XOR operations rather than complex algorithms or data structures.

Q: Number Complement Python/Java solution

In Python or Java, compute the mask using the bit length of the number: mask = (1 << num.bit_length()) - 1 in Python or (1 << (Integer.toBinaryString(num).length())) - 1 in Java. Return num ^ mask to flip all bits up to the most significant bit.

Q: How to solve Number Complement in O(1)?

Compute the number of bits in num using a bit-length operation. Create a mask with (1 << bits) - 1 so all bits are set to 1 up to the most significant bit. The complement is then num ^ mask, which flips every bit in constant time.

Q: What is the best approach for Number Complement?

The most common approach uses bit manipulation with a mask of all 1s covering the length of the number's binary representation. After building the mask, compute the complement using XOR: num ^ mask. This flips only the relevant bits and runs in O(log n) time with O(1) space.

Q: Is Number Complement asked at Google/Amazon/Meta?

Number Complement is a classic bit manipulation problem commonly used in coding interviews to test understanding of binary representation and XOR operations. Variants of this problem appear in interview preparation sets for companies like Amazon and Google.

Q: What data structure is used in Number Complement?

The solution does not require traditional data structures like arrays or hash maps. It relies purely on bit manipulation operations such as bit shifts, XOR, and mask creation to flip the bits of the integer.

Q: What is the time complexity of Number Complement?

The typical mask-building approach runs in O(log n) time because it processes each bit of the number once. Space complexity is O(1) since only a few integer variables are used. If the language provides a direct bit-length function, the operation effectively becomes O(1).

The problem

The complement of an integer is the integer you get when you flip all the 0's to 1's and all the 1's to 0's in its binary representation.

For example, The integer 5 is "101" in binary and its complement is "010" which is the integer 2.

Given an integer num, return its complement.

Example 1:

Input: num = 5
Output: 2
Explanation: 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
Explanation: 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 < 2³¹

Note: This question is the same as 1009: https://leetcode.com/problems/complement-of-base-10-integer/

Approach overview

Problem Overview: You’re given a positive integer num. The task is to flip every bit in its binary representation, but only up to the most significant bit. Leading zeros are not part of the number, so the complement only affects the bits that actually appear in the binary form.

Approach 1: Bit Manipulation with Mask (O(log n) time, O(1) space)

This approach constructs a bitmask containing all 1s that match the length of num's binary representation. For example, if num = 5 (101 in binary), the mask becomes 111. You build the mask by repeatedly left-shifting and adding 1 until it covers the highest set bit of num. Once the mask is ready, compute the complement using a bitwise XOR: num ^ mask. XOR flips each bit where the mask has 1. This solution relies purely on bit manipulation and works in O(log n) time because the mask is built across the number of bits.

Approach 2: Using Bit Length to Create Mask (O(1) time, O(1) space)

Instead of iteratively building the mask, you can compute the number of bits directly using the bit length of num. If the binary length is k, a mask of k ones is (1 << k) - 1. For instance, if num = 5, its bit length is 3, and the mask becomes (1 << 3) - 1 = 7 (111). The complement is again num ^ mask. This method avoids loops and uses a simple shift operation from bit manipulation combined with bitwise operations. It’s concise and commonly used in production code when the language provides a built‑in bit length function.

Recommended for interviews: The mask construction method is the one most interviewers expect. It demonstrates that you understand how binary representations work and how to manipulate them with shifts and XOR. The bit-length formula is slightly cleaner and faster in practice, but both approaches rely on the same insight: create a mask of all 1s covering the highest set bit, then flip bits using XOR.

Approach 1: Bit Manipulation with Mask

This approach uses bit manipulation to find the complement. The idea is to create a mask that has the same number of bits set to 1 as the number. By XORing the number with this mask, we effectively flip all the bits.

To create the mask, we can shift 1 left until it exceeds the number and then subtract 1 from it.

Python

def find_complement(num):
    mask = ~0
    while num & mask:
        mask <<= 1
    return ~mask & ~num

print(find_complement(5))  # Output: 2
print(find_complement(1))  # Output: 0

Java

public class Main {
    public static int findComplement(int num) {
        int mask = ~0;
        while ((num & mask) != 0) mask <<= 1;
        return ~mask & ~num;
    }
    
    public static void main(String[] args) {
        System.out.println(findComplement(5)); // Output: 2
        System.out.println(findComplement(1)); // Output: 0
    }
}

C++

#include <iostream>

using namespace std;

int findComplement(int num) {
    unsigned mask = ~0;
    while (num & mask) mask <<= 1;
    return ~mask & ~num;
}

int main() {
    cout << findComplement(5) << endl; // Output: 2
    cout << findComplement(1) << endl; // Output: 0
    return 0;
}

JavaScript

function findComplement(num) {
    let mask = ~0;
    while (num & mask) mask <<= 1;
    return ~mask & ~num;
}

console.log(findComplement(5)); // Output: 2
console.log(findComplement(1)); // Output: 0;

#include <stdio.h>

int findComplement(int num) {
    unsigned mask = ~0;
    while (num & mask) mask <<= 1;
    return ~mask & ~num;
}

int main() {
    printf("%d\n", findComplement(5)); // Output: 2
    printf("%d\n", findComplement(1)); // Output: 0
    return 0;
}

using System;

class Program {
    public static int FindComplement(int num) {
        int mask = ~0;
        while ((num & mask) != 0) mask <<= 1;
        return ~mask & ~num;
    }

    static void Main() {
        Console.WriteLine(FindComplement(5)); // Output: 2
        Console.WriteLine(FindComplement(1)); // Output: 0
    }
}

This Python function uses a similar approach with a mask initially set to all 1s, then shifted and XORed with the input number's negation.

Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Try this approach in the editor

Approach 2: Using Bit Length to Create Mask

This approach derives a mask by using the bit length of the number. We create a mask by taking 2ⁿ - 1, where n is the bit size of the number.

The result of the XOR between num and mask gives the complement.

Python

def find_complement(num):
    mask = 1
    while mask <= num:
        mask <<= 1
    return (mask - 1) ^ num

print(find_complement(5))  # Output: 2
print(find_complement(1))  # Output: 0

Java

public class Main {
    public static int findComplement(int num) {
        int mask = 1;
        while (mask <= num) mask <<= 1;
        return (mask - 1) ^ num;
    }
    
    public static void main(String[] args) {
        System.out.println(findComplement(5)); // Output: 2
        System.out.println(findComplement(1)); // Output: 0
    }
}

C++

#include <iostream>

using namespace std;

int findComplement(int num) {
    unsigned mask = 1;
    while (mask <= num) mask <<= 1;
    return (mask - 1) ^ num;
}

int main() {
    cout << findComplement(5) << endl; // Output: 2
    cout << findComplement(1) << endl; // Output: 0
    return 0;
}

JavaScript

function findComplement(num) {
    let mask = 1;
    while (mask <= num) mask <<= 1;
    return (mask - 1) ^ num;
}

console.log(findComplement(5)); // Output: 2
console.log(findComplement(1)); // Output: 0;

#include <stdio.h>

int findComplement(int num) {
    unsigned mask = 1;
    while (mask <= num) mask <<= 1;
    return (mask - 1) ^ num;
}

int main() {
    printf("%d\n", findComplement(5)); // Output: 2
    printf("%d\n", findComplement(1)); // Output: 0
    return 0;
}

using System;

class Program {
    public static int FindComplement(int num) {
        int mask = 1;
        while (mask <= num) mask <<= 1;
        return (mask - 1) ^ num;
    }

    static void Main() {
        Console.WriteLine(FindComplement(5)); // Output: 2
        Console.WriteLine(FindComplement(1)); // Output: 0
    }
}

This Python function computes the mask based on the input's bit length, then returns the complement by XORing.

Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Try this approach in the editor

Approach 3: Bit Manipulation

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

First, we find the highest bit of 1 in the binary representation of num, and the position is denoted as k.

Then, we construct a binary number, where the k-th bit is 0 and the rest of the lower bits are 1, which is 2^k - 1;

Finally, we perform XOR operation on num and the constructed binary number to get the answer.

The time complexity is O(log num), where num is the input integer. The space complexity is O(1).

TypeScript

function findComplement(num: number): number {
    return num ^ (2 ** num.toString(2).length - 1);
}

func findComplement(num int) int {
	return num ^ ((1 << bits.Len(uint(num))) - 1)
}

Try this approach in the editor

Approach 4: Bit Manipulation. Inversion + AND

TypeScript

function findComplement(num: number): number {
    return ~num & (2 ** num.toString(2).length - 1);
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Bit Manipulation with Mask	Time Complexity: O(1) Space Complexity: O(1)
Using Bit Length to Create Mask	Time Complexity: O(1) Space Complexity: O(1)
Bit Manipulation	–
Bit Manipulation. Inversion + AND	–

Complexity analysis

Approach	Time	Space	When to Use
Bit Manipulation with Mask	O(log n)	O(1)	General interview solution when you want to explicitly build the mask using shifts.
Using Bit Length to Create Mask	O(1)	O(1)	When the language provides a built-in bit length function and you want a concise implementation.

Frequently asked questions

Is Number Complement easy or hard?

Number Complement is classified as an Easy problem on LeetCode. The challenge mainly tests basic understanding of binary numbers, bit masks, and XOR operations rather than complex algorithms or data structures.

Number Complement Python/Java solution

In Python or Java, compute the mask using the bit length of the number: mask = (1 << num.bit_length()) - 1 in Python or (1 << (Integer.toBinaryString(num).length())) - 1 in Java. Return num ^ mask to flip all bits up to the most significant bit.

How to solve Number Complement in O(1)?

Compute the number of bits in num using a bit-length operation. Create a mask with (1 << bits) - 1 so all bits are set to 1 up to the most significant bit. The complement is then num ^ mask, which flips every bit in constant time.

What is the best approach for Number Complement?

The most common approach uses bit manipulation with a mask of all 1s covering the length of the number's binary representation. After building the mask, compute the complement using XOR: num ^ mask. This flips only the relevant bits and runs in O(log n) time with O(1) space.

Is Number Complement asked at Google/Amazon/Meta?

Number Complement is a classic bit manipulation problem commonly used in coding interviews to test understanding of binary representation and XOR operations. Variants of this problem appear in interview preparation sets for companies like Amazon and Google.

What data structure is used in Number Complement?

The solution does not require traditional data structures like arrays or hash maps. It relies purely on bit manipulation operations such as bit shifts, XOR, and mask creation to flip the bits of the integer.

What is the time complexity of Number Complement?

The typical mask-building approach runs in O(log n) time because it processes each bit of the number once. Space complexity is O(1) since only a few integer variables are used. If the language provides a direct bit-length function, the operation effectively becomes O(1).

Number Complement solution and explanation

The problem

Approach overview

Approach 1: Bit Manipulation with Mask

Approach 2: Using Bit Length to Create Mask

Approach 3: Bit Manipulation

Approach 4: Bit Manipulation. Inversion + AND

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Number Complement solution and explanation

The problem

Approach overview

Approach 1: Bit Manipulation with Mask

Approach 2: Using Bit Length to Create Mask

Approach 3: Bit Manipulation

Approach 4: Bit Manipulation. Inversion + AND

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems