Complement of Base 10 Integer

LeetCode 1054 | Difficulty: Easy

Easy

Problem Description

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 < 10^9`

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

Topics: Bit Manipulation

---

Approach

Bit Manipulation

Operate directly on binary representations. Key operations: AND (&), OR (|), XOR (^), NOT (~), shifts (<<, >>). XOR is especially useful: a ^ a = 0, a ^ 0 = a.

When to use

Finding unique elements, power of 2 checks, subset generation, toggling flags.

---

Solutions

Solution 1: C# (Best: 56 ms)

Metric	Value
Runtime	56 ms
Memory	25.4 MB
Date	2021-11-25

Solution

public class Solution {
    public int BitwiseComplement(int n) {
        int c = 1;
        while(c < n)
        {
            c = (c << 1) + 1;
        }
        return n^c;
    }
}

---

Complexity Analysis

Approach	Time	Space
Bit Manipulation	$O(n) or O(1)$	$O(1)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• LeetCode provides 1 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: A binary number plus its complement will equal 111....111 in binary. Also, N = 0 is a corner case.