Complement of Base 10 Integer solution and explanation
Google
9 more videos on this problem
complement of base 10 integer | complement of base 10 integer leetcode | leetcode 1009 | bitwiseNaresh Gupta · 8:13 · 5K views
Complement of Base 10 Integer | 3 Detailed Approaches | Leetcode 1009 | codestorywithMIKcodestorywithMIK · 16:09 · 5K views
Complement of Base 10 Integer LeetCode | Leetcode 1009 | Leetcode October ChallengeCode Bashers · 9:16 · 3K views
Complement of Base 10 Integer | Leetcode 1009 | Live coding session 🔥🔥🔥 | O(1) Bit ManipulationCoding Decoded · 3:38 · 1K views
Complement of Base 10 Integer | Bits | 1009 LeetCode | Day 04CodeWithSunny · 10:24 · 1K views
Complement of Base 10 Integer | Leet code 1009 | Theory explained + Python codeSai Anish Malla · 10:22 · 1K views
Complement of Base 10 Integer Leetcode 1009 videoEasyLeetcode · 6:23 · 731 views
Leetcode - Complement of Base 10 Integer (Python)Timothy H Chang · 3:36 · 632 views
1009. Complement of Base 10 Integer | Leetcode Daily - PythonLeetcode Daily · 7:17 · 440 views
Daily Leetcode #644: Jan 04, 2022 - 1009. Complement of Base 10 IntegerProgramming Live with Larry · 2:35 · 203 views
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
5is"101"in binary and its complement is"010"which is the integer2.
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.
def bitwiseComplement(n):
if n == 0:
return 1
mask = 0
m = n
while m:
mask = (mask << 1) | 1
m >>= 1
return (~n) & mask
print(bitwiseComplement(5))public class Solution {
public int bitwiseComplement(int n) {
if (n == 0) return 1;
int mask = 0;
int m = n;
while (m != 0) {
mask = (mask << 1) | 1;
m >>= 1;
}
return (~n) & mask;
}
public static void main(String[] args) {
Solution sol = new Solution();
int n = 5;
System.out.println(sol.bitwiseComplement(n));
}
}#include <iostream>
using namespace std;
int bitwiseComplement(int n) {
if (n == 0) return 1;
int mask = 0;
unsigned int m = n;
while (m) {
mask = (mask << 1) | 1;
m >>= 1;
}
return (~n) & mask;
}
int main() {
int n = 5;
cout << bitwiseComplement(n) << endl;
return 0;
}function bitwiseComplement(n) {
if (n === 0) return 1;
let mask = 0;
let m = n;
while (m !== 0) {
mask = (mask << 1) | 1;
m >>= 1;
}
return (~n) & mask;
}
console.log(bitwiseComplement(5));#include <stdio.h>
int bitwiseComplement(int n){
if (n == 0) return 1;
int mask = 0;
unsigned int m = n;
while (m) {
mask = (mask << 1) | 1;
m >>= 1;
}
return (~n) & mask;
}
int main() {
int n = 5;
printf("%d", bitwiseComplement(n));
return 0;
}using System;
public class Solution {
public int BitwiseComplement(int n) {
if (n == 0) return 1;
int mask = 0;
int m = n;
while (m != 0) {
mask = (mask << 1) | 1;
m >>= 1;
}
return (~n) & mask;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int n = 5;
Console.WriteLine(sol.BitwiseComplement(n));
}
}This Python function uses the same approach as previously discussed solutions. A mask of 1s is created, and the complement of n is computed by XOR against this mask.
Time Complexity: O(log(n)) due to needing to determine the number of bits.
Space Complexity: O(1), since no additional space is needed outside fixed variables.
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.
def bitwiseComplement(n):
if n == 0:
return 1
mask = 1
while mask <= n:
mask <<= 1
return (mask - 1) ^ n
print(bitwiseComplement(5))public class Solution {
public int bitwiseComplement(int n) {
if (n == 0) return 1;
int mask = 1;
while (mask <= n) mask <<= 1;
return (mask - 1) ^ n;
}
public static void main(String[] args) {
Solution sol = new Solution();
int n = 5;
System.out.println(sol.bitwiseComplement(n));
}
}#include <iostream>
using namespace std;
int bitwiseComplement(int n) {
if (n == 0) return 1;
int mask = 1;
while (mask <= n) mask <<= 1;
return (mask - 1) ^ n;
}
int main() {
int n = 5;
cout << bitwiseComplement(n) << endl;
return 0;
}function bitwiseComplement(n) {
if (n === 0) return 1;
let mask = 1;
while (mask <= n) {
mask <<= 1;
}
return (mask - 1) ^ n;
}
console.log(bitwiseComplement(5));#include <stdio.h>
int bitwiseComplement(int n){
if (n == 0) return 1;
int mask = 1;
while (mask <= n) mask <<= 1;
return (mask - 1) ^ n;
}
int main() {
int n = 5;
printf("%d", bitwiseComplement(n));
return 0;
}using System;
public class Solution {
public int BitwiseComplement(int n) {
if (n == 0) return 1;
int mask = 1;
while (mask <= n) mask <<= 1;
return (mask - 1) ^ n;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int n = 5;
Console.WriteLine(sol.BitwiseComplement(n));
}
}The Python function builds the mask by setting a loop condition within power boundaries, performing all computations efficiently through combined mathematical and bitwise logic.
Time Complexity: O(log(n)) because we compute up to the nearest power of two.
Space Complexity: O(1) due to fixed computational requirements.
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).
function bitwiseComplement(n: number): number {
if (n === 0) {
return 1;
}
let ans = 0;
for (let i = 0; n; n >>= 1) {
ans |= ((n & 1) ^ 1) << i++;
}
return ans;
}func bitwiseComplement(n int) (ans int) {
if n == 0 {
return 1
}
for i := 0; n != 0; n >>= 1 {
ans |= (n&1 ^ 1) << i
i++
}
return
}impl Solution {
pub fn bitwise_complement(mut n: i32) -> i32 {
if n == 0 {
return 1;
}
let mut ans = 0;
let mut i = 0;
while n != 0 {
ans |= ((n & 1) ^ 1) << i;
n >>= 1;
i += 1;
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Bit Manipulation Using Mask | Time Complexity: O(log(n)) due to needing to determine the number of bits. |
| Bit Manipulation Using Math | Time Complexity: O(log(n)) because we compute up to the nearest power of two. |
| Bit Manipulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bit Manipulation Using Mask | O(log n) | O(1) | Best general solution. Efficient and uses standard bitwise operations expected in interviews. |
| Bit Manipulation Using Math | O(log n) | O(1) | Useful for understanding how complements form by flipping each binary digit. |
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).