Skip to main content
Talentd

Complement of Base 10 Integer - Solution & Explanation

EasyBit Manipulation15 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 n, return its complement.

 

Example 1:

Input: n = 5
Output: 2
Explanation: 5 is "101" in binary, with complement "010" in binary, which is 2 in base-10.

Example 2:

Input: n = 7
Output: 0
Explanation: 7 is "111" in binary, with complement "000" in binary, which is 0 in base-10.

Example 3:

Input: n = 10
Output: 5
Explanation: 10 is "1010" in binary, with complement "0101" in binary, which is 5 in base-10.

 

Constraints:

  • 0 <= n < 109

 

Note: This question is the same as 476: https://leetcode.com/problems/number-complement/

Approach Overview

Problem Overview: Given a non‑negative integer n, return its complement. The complement flips every bit in the binary representation of n (0 becomes 1, 1 becomes 0) while ignoring leading zeros. For example, 5 (binary 101) becomes 2 (binary 010).

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

This method constructs a bit mask that covers exactly the number of bits used by n. First determine the bit length of n by shifting or repeatedly doubling until the mask exceeds the value. A mask like (1 << k) - 1 creates a number with k ones in binary. Once you have the mask, compute the complement with mask ^ n. The XOR flips all bits within that range while leaving higher bits untouched. This approach uses direct bit manipulation operations and runs in O(log n) time because the number of bits in n grows logarithmically.

The key insight: you cannot simply apply ~n because it flips all 32 or 64 bits depending on the language. Creating a mask restricts the operation to the meaningful portion of the binary representation. This is the most common implementation used in interview solutions.

Approach 2: Bit Manipulation Using Math (O(log n) time, O(1) space)

This version builds the complement bit by bit using arithmetic. Iterate through the binary digits of n from least significant to most significant. For each step, check the current bit with n % 2. If the bit is 0, add the corresponding power of two to the result. Then divide n by two and continue. Track the current bit position with a multiplier that doubles each iteration. The resulting number is the complement.

This approach relies more on math-based bit extraction rather than direct bitwise masks. It is useful if you want to explicitly see how each bit is flipped and reconstructed. The complexity remains O(log n) because you process each binary digit once.

Recommended for interviews: The mask-based solution is typically expected. It demonstrates comfort with bitwise operations such as shifts, XOR, and mask construction. The math approach still shows understanding of binary representation but is slightly more verbose. A strong answer explains why ~n alone is incorrect and how the mask limits the complement to the actual bit length.

Approach 1: Bit Manipulation Using Mask

This approach involves calculating a mask of the same bit length as the number and then using XOR to flip all the bits. The mask is calculated as a sequence of 1s of the same length as the binary representation of the number. For any number 'n', the mask would be computed as (1 << number_of_bits) - 1.

The function bitwiseComplement checks if the input number is zero, in which case it returns 1 as the complement of 0 is 1. For other numbers, it calculates a mask with all bits set to 1 up to the most significant bit of the number. The complement is then calculated by XORing this mask with the number, flipping all its bits.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log(n)) as we are shifting bits for the length of the number.
Space Complexity: O(1) since we are using a constant space.

Try this approach in the editor →

Approach 2: Bit Manipulation Using Math

In this approach, instead of calculating a mask using shifts, we use mathematical expressions. We calculate the highest power of 2 greater than n, subtract 1 to get a mask with all 1s up to the highest bit set in n. This mask is then XORed with n for the result.

This C function calculates (2^x - 1) by left-shifting the mask variable until it is larger than n, then uses XOR to find the complement of n. It's a compact design that minimizes operations while still achieving the same result.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log(n)) for shifting mask while determining the next power of 2.
Space Complexity: O(1) as only simple variables are used.

Try this approach in the editor →

Approach 3: Bit Manipulation

First, we check if n is 0. If it is, we return 1.

Next, we define two variables ans and i, both initialized to 0. Then we iterate through n. In each iteration, we set the i-th bit of ans to the inverse of the i-th bit of n, increment i by 1, and right shift n by 1.

Finally, we return ans.

The time complexity is O(log n), where n is the given decimal number. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Bit Manipulation Using Mask

Time Complexity: O(log(n)) as we are shifting bits for the length of the number.
Space Complexity: O(1) since we are using a constant space.

Bit Manipulation Using Math

Time Complexity: O(log(n)) for shifting mask while determining the next power of 2.
Space Complexity: O(1) as only simple variables are used.

Bit Manipulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Bit Manipulation Using MaskO(log n)O(1)Best general solution. Efficient and uses standard bitwise operations expected in interviews.
Bit Manipulation Using MathO(log n)O(1)Useful for understanding how complements form by flipping each binary digit.

Video Solution

complement of base 10 integer | complement of base 10 integer leetcode | leetcode 1009 | bitwise • Naresh Gupta • 5,667 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Complement of Base 10 Integer easy or hard?
Complement of Base 10 Integer is categorized as an Easy problem on LeetCode with an acceptance rate above 60%. The main challenge is understanding why a mask is required instead of using the bitwise NOT operator directly.
Complement of Base 10 Integer Python/Java solution
In Python or Java, compute the bit length of n, create a mask like (1 << k) - 1, and return mask ^ n. Python also provides n.bit_length() to determine k directly. Java implementations typically use a loop or shifting to determine the mask size.
How to solve Complement of Base 10 Integer in O(log n)?
Compute the number of bits in n and build a mask containing only 1s for those positions. A common formula is mask = (1 << k) - 1 where k is the bit length. The complement is then mask ^ n, which flips every bit within the mask range.
What is the best approach for Complement of Base 10 Integer?
The most efficient approach uses bit manipulation with a mask. First compute a mask with all bits set to 1 for the length of the number, such as (1 << k) - 1 where k is the number of bits in n. Then return mask XOR n to flip only the relevant bits. This runs in O(log n) time and O(1) space.
Is Complement of Base 10 Integer asked at Google/Amazon/Meta?
Bit manipulation problems similar to this appear in interviews at companies like Google, Amazon, and Meta. They are often used to test understanding of binary representation, bit masks, and XOR operations. The difficulty is easy but the concept appears frequently in screening rounds.
What data structure is used in Complement of Base 10 Integer?
No complex data structure is required. The problem relies purely on bitwise operations such as XOR, shifts, and masks. Some implementations use arithmetic operations to extract bits, but the core concept belongs to bit manipulation.
What is the time complexity of Complement of Base 10 Integer?
The time complexity is O(log n) because the algorithm processes the binary length of the number. Whether you build a mask or iterate through bits using division or shifts, the number of steps equals the number of bits in n. Space complexity is O(1).

Ready to solve this problem?

Practice Complement of Base 10 Integer with our built-in code editor and test cases.

Practice on FleetCode
Previous

Divide Two Integers

Next

Add Binary