Skip to main content
Talentd

Number Complement - Solution & Explanation

EasyBit Manipulation13 min readAsked at: Amazon, Meta, Google +2
Practice this problem

Problem Statement

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 < 231

 

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.

We create a mask with all bits set to 1 initially. Then, we shift it left until it has more bits than the input number's binary length. Finally, we XOR the input number with the negated mask.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(1), the operations are done in constant time as the number of bits is fixed.
Space Complexity: O(1), no additional space is used.

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 2n - 1, where n is the bit size of the number.

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

In this C program, we calculate a mask such that all bits below the highest bit of num are 1. We then XOR num with this mask to get the complement.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

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).

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Approach 4: Bit Manipulation. Inversion + AND

Code

TypeScriptJavaScript

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Bit Manipulation with Mask

Time Complexity: O(1), the operations are done in constant time as the number of bits is fixed.
Space Complexity: O(1), no additional space is used.

Using Bit Length to Create Mask

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

Bit Manipulation—
Bit Manipulation. Inversion + AND—

Detailed Complexity Analysis

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

Video Solution

Number complement | Leetcode #476 • Techdose • 18,147 views views

Watch 9 more video solutions →

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).

Ready to solve this problem?

Practice Number Complement with our built-in code editor and test cases.

Practice on FleetCode
Previous

Divide Two Integers

Next

Add Binary