# Complement of Base 10 Integer
**Difficulty:** EASY
[External](https://leetcode.com/problems/complement-of-base-10-integer)
Canonical: https://scaleengineer.com/dsa/problems/complement-of-base-10-integer
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Companies:** [Snap](https://scaleengineer.com/companies/snap), [Cloudera](https://scaleengineer.com/companies/cloudera)
---
## 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 `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/>

# Approaches
## String Conversion and Manipulation
This approach involves converting the number to its binary string representation, flipping the bits in the string, and then converting the modified binary string back to an integer. It's a straightforward implementation that directly follows the problem's definition.
**Time:** O(log n). The number of bits in `n` is proportional to `log n`. Converting to and from a string, and iterating through it, all take time proportional to the number of bits. · **Space:** O(log n). We need extra space to store the binary string representation and the `StringBuilder`. The length of the binary string is proportional to log n.
**Pros:** Easy to understand and implement, as it directly follows the problem definition.; Leverages high-level built-in functions, making the code readable.
**Cons:** Less efficient in terms of both time and space compared to bitwise manipulation approaches.; Involves overhead from string object creation, manipulation, and parsing.
### Explanation
The core idea is to leverage built-in functions for number-to-string and string-to-number conversions.

1.  First, we convert the input integer `n` into its binary string equivalent using a function like `Integer.toBinaryString(n)`.
2.  Then, we iterate through this string. For each character, we flip it: '0' becomes '1' and '1' becomes '0'. We build a new string with these flipped bits using a `StringBuilder` for efficiency.
3.  Finally, we parse this new binary string back into a base-10 integer using `Integer.parseInt(complementString, 2)`.

For example, if `n = 5`, `Integer.toBinaryString(5)` gives `"101"`. We flip the bits to get `"010"`. `Integer.parseInt("010", 2)` results in `2`.

```java
class Solution {
    public int bitwiseComplement(int n) {
        if (n == 0) {
            return 1;
        }
        String binaryString = Integer.toBinaryString(n);
        StringBuilder complementString = new StringBuilder();
        for (char c : binaryString.toCharArray()) {
            if (c == '0') {
                complementString.append('1');
            } else {
                complementString.append('0');
            }
        }
        return Integer.parseInt(complementString.toString(), 2);
    }
}
```
### Algorithm
- Handle the edge case: if `n` is 0, return 1.
- Convert the integer `n` to its binary string representation using `Integer.toBinaryString(n)`.
- Initialize an empty `StringBuilder` to store the complement binary string.
- Iterate through each character of the binary string.
- If the character is '1', append '0' to the `StringBuilder`.
- If the character is '0', append '1' to the `StringBuilder`.
- After the loop, convert the `StringBuilder` to a string.
- Parse the complement binary string back to an integer (base 10) using `Integer.parseInt(complementString, 2)` and return it.

## Iterative Bitwise Manipulation
This method avoids string conversions by directly manipulating the bits of the integer. It iterates through each bit of the input number, calculates its complement, and constructs the result number bit by bit.
**Time:** O(log n). The loop runs once for each bit in the binary representation of `n`. The number of bits is `floor(log2(n)) + 1`. · **Space:** O(1). We only use a few extra variables (`result`, `powerOfTwo`, `tempN`), regardless of the size of `n`.
**Pros:** More efficient than the string approach, especially in terms of space.; Works directly with the integer representation, avoiding string conversion overhead.
**Cons:** Slightly more complex to reason about than the direct string conversion.; Still requires a loop, making it less efficient than a constant-time bitmask approach.
### Explanation
We process the input number `n` one bit at a time, from the least significant bit (LSB) to the most significant bit (MSB).
We use a `result` variable to build the complement number and a `powerOfTwo` variable to place the complemented bits in their correct positions.

In each step of the loop:
1.  We extract the LSB of `n` using the bitwise AND operation: `n & 1`.
2.  We flip this bit. If the bit is 1, its complement is 0. If it's 0, its complement is 1. This can be calculated as `1 - (n & 1)`.
3.  We multiply this flipped bit by the current `powerOfTwo` and add it to our `result`.
4.  We then right-shift `n` by one (`n >>= 1`) to discard the LSB and process the next bit in the following iteration.
5.  We update `powerOfTwo` by left-shifting it by one (`powerOfTwo <<= 1`), effectively doubling it for the next bit's position.

The loop continues until `n` becomes 0, meaning all its bits have been processed. A special case is `n = 0`, whose complement is `1`.

```java
class Solution {
    public int bitwiseComplement(int n) {
        if (n == 0) {
            return 1;
        }
        int result = 0;
        int powerOfTwo = 1;
        int tempN = n;
        while (tempN > 0) {
            // Get the last bit and flip it
            int lastBit = tempN & 1;
            int flippedBit = 1 - lastBit;
            
            // Add to result
            result += flippedBit * powerOfTwo;
            
            // Move to the next bit
            powerOfTwo <<= 1;
            tempN >>= 1;
        }
        return result;
    }
}
```
### Algorithm
- Handle the edge case: if `n` is 0, return 1.
- Initialize `result = 0` and `powerOfTwo = 1`.
- Create a temporary copy of `n` to iterate with.
- Loop while the temporary number is greater than 0.
- Extract the last bit using `(temp_n & 1)`.
- Flip the bit (e.g., `1 - last_bit`).
- Add `flipped_bit * powerOfTwo` to `result`.
- Update `powerOfTwo` by left-shifting it by 1 (`powerOfTwo <<= 1`).
- Update the temporary number by right-shifting it by 1 (`temp_n >>= 1`).
- After the loop, return `result`.

## Bitwise XOR with a Mask
This is the most efficient approach. It relies on the property that for any number `n`, `n XOR mask = complement`, where `mask` is a number with the same bit length as `n` but with all bits set to 1. The problem then reduces to finding this mask and performing a single XOR operation.
**Time:** O(1). Using `Integer.highestOneBit` and other bitwise operations are typically single-instruction, constant-time operations on most hardware. · **Space:** O(1). No extra space proportional to the input size is required.
**Pros:** Extremely fast and efficient, with constant time complexity.; Concise and elegant solution for those familiar with bitwise operations.
**Cons:** Can be less intuitive for beginners compared to the string-based approach.; Requires understanding of bitwise operators (XOR, shifts) and how to construct a bitmask.
### Explanation
The key insight is that flipping bits is equivalent to a bitwise XOR operation with a mask of all 1s. For example, for `n = 5` (binary `101`), the mask should be `111`. `101 XOR 111` gives `010`, which is the complement.

The main task is to construct this mask. The mask must have the same number of bits as the binary representation of `n`.

A clever and fast way to create this mask in Java is to use `Integer.highestOneBit(n)`. This function returns a value with only the most significant bit of `n` set. For `n=10` (`1010`), `Integer.highestOneBit(10)` is 8 (`1000`). The full mask can be constructed by left-shifting this result by one and subtracting one: `(Integer.highestOneBit(n) << 1) - 1`. This creates a mask of all ones with the correct length (e.g., `(8 << 1) - 1 = 16 - 1 = 15`, which is `1111` in binary).

Once the mask is found, the complement is simply `mask ^ n`. The edge case `n = 0` must be handled separately, as its complement is `1`.

```java
class Solution {
    public int bitwiseComplement(int n) {
        if (n == 0) {
            return 1;
        }
        // Find a mask with the same number of bits as n, all set to 1.
        // e.g., n = 5 (101), highestOneBit is 4 (100).
        // mask = (4 << 1) - 1 = 8 - 1 = 7 (111).
        int mask = (Integer.highestOneBit(n) << 1) - 1;
        
        // The complement is n XOR mask.
        // e.g., 5 ^ 7 = 101 ^ 111 = 010 = 2.
        return n ^ mask;
    }
}
```
### Algorithm
- Handle the edge case: if `n` is 0, return 1.
- Create a bitmask that has the same number of bits as `n` and all bits are set to '1'.
  - Find the highest set bit using `Integer.highestOneBit(n)`.
  - The mask is `(Integer.highestOneBit(n) << 1) - 1`.
- Perform a bitwise XOR operation between `n` and the `mask`.
- Return the result of the XOR operation.

# Solutions
### Java

```java
class Solution {
public
  int bitwiseComplement(int n) {
    if (n == 0) {
      return 1;
    }
    int ans = 0;
    boolean find = false;
    for (int i = 30; i >= 0; --i) {
      int b = n & (1 << i);
      if (!find && b == 0) {
        continue;
      }
      find = true;
      if (b == 0) {
        ans |= (1 << i);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int bitwiseComplement(int n) {
    if (n == 0)
      return 1;
    int ans = 0;
    bool find = false;
    for (int i = 30; i >= 0; --i) {
      int b = n & (1 << i);
      if (!find && b == 0)
        continue;
      find = true;
      if (b == 0)
        ans |= (1 << i);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def bitwiseComplement(self, n: int) -> int: if n == 0: return 1 ans = 0 find = False for i in range(30, - 1, - 1): b = n & (1 << i) if not find and b == 0: continue find = True if b == 0: ans |= 1 << i return ans

```