# Number Complement
**Difficulty:** EASY
[External](https://leetcode.com/problems/number-complement)
Canonical: https://scaleengineer.com/dsa/problems/number-complement
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Companies:** [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 `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/>

# Approaches
## Approach 1: String Conversion
This approach is the most straightforward, as it directly follows the problem's definition. It involves converting the number to a binary string, flipping the characters of the string ('0's to '1's and vice-versa), and then converting the modified binary string back to an integer.
**Time:** O(log n). The time complexity is dominated by the conversion to and from the binary string, as well as the iteration. The number of bits in `num` is proportional to log(num). · **Space:** O(log n). The space is required to store the binary string representation of the number `num` and the `StringBuilder`. The length of the binary string is proportional to log(num).
**Pros:** Very easy to understand and implement.; The logic directly maps to the problem description.
**Cons:** Relatively inefficient due to the overhead of creating and manipulating string objects.; Involves multiple conversions (integer to string, string to integer) which are computationally more expensive than bitwise operations.
### Explanation
The core of this method lies in leveraging built-in functions for number-to-string and string-to-number conversions. First, we get the binary representation of `num` as a string. Then, we iterate over this string, building a new string which is the bitwise complement of the original. Finally, this new binary string is parsed back into an integer, which is our result.

```java
class Solution {
    public int findComplement(int num) {
        String binaryString = Integer.toBinaryString(num);
        StringBuilder complementBuilder = new StringBuilder();
        for (char c : binaryString.toCharArray()) {
            if (c == '1') {
                complementBuilder.append('0');
            } else {
                complementBuilder.append('1');
            }
        }
        return Integer.parseInt(complementBuilder.toString(), 2);
    }
}
```
### Algorithm
- Convert the input integer `num` to its binary string representation using a built-in function like `Integer.toBinaryString(num)`.
- Create a new `StringBuilder` to construct the complemented binary string.
- Iterate through each character of the original 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 this new binary string back to an integer using base 2, for example, with `Integer.parseInt(complementedString, 2)`.
- Return the final integer.

## Approach 2: Iterative Bit-by-Bit Calculation
A more optimized approach is to avoid string conversions and work directly with the bits of the integer. We can process the number bit by bit, from least significant to most significant. In each step, we flip the current bit and add its corresponding value to a running total which will be our final result.
**Time:** O(log n). The loop runs once for each bit in the binary representation of `num`. The number of bits is proportional to log(num). · **Space:** O(1). We only use a few variables to store the result and loop counters, regardless of the size of the input number.
**Pros:** More efficient than the string-based approach.; Uses constant extra space, O(1).
**Cons:** Requires a loop that iterates through each bit, which is less performant than a constant-time bitmasking solution.
### Explanation
This method iteratively builds the complement number. We use a loop that continues as long as there are bits left to process in the input number. Inside the loop, we isolate the last bit, flip it, and then add its positional value (e.g., 1, 2, 4, 8...) to our result. We use a `powerOfTwo` variable, starting at 1 and doubling in each iteration, to calculate this positional value. The input number is right-shifted in each iteration to expose the next bit.

```java
class Solution {
    public int findComplement(int num) {
        int result = 0;
        long powerOfTwo = 1; // Use long to avoid overflow for large num
        int temp = num;

        while (temp > 0) {
            // Get the least significant bit (0 or 1)
            int lsb = temp & 1;
            // Flip the bit (0 becomes 1, 1 becomes 0)
            int flippedLsb = lsb ^ 1;
            // Add the value of the flipped bit to the result
            result += flippedLsb * powerOfTwo;
            
            // Move to the next bit position
            powerOfTwo <<= 1;
            temp >>= 1;
        }
        
        // Handle the edge case where num is 0, though constraints prevent this.
        // If num was 0, the loop wouldn't run, returning 0. The complement of 0 is 1.
        // A simple fix would be `if (num == 0) return 1;`
        return result;
    }
}
```
### Algorithm
- Initialize `result` to 0 and `powerOfTwo` to 1. `powerOfTwo` will track the value of the current bit position (1, 2, 4, ...).
- Make a copy of `num` to iterate with, let's call it `temp`.
- Loop while `temp` is greater than 0:
  - Extract the least significant bit (LSB) of `temp` using `temp & 1`.
  - Flip the LSB: `flippedBit = lsb ^ 1`.
  - Add the flipped bit's value to the result: `result += flippedBit * powerOfTwo`.
  - Update `powerOfTwo` for the next position by left-shifting it: `powerOfTwo <<= 1`.
  - Update `temp` by right-shifting it to process the next bit: `temp >>= 1`.
- After the loop terminates, `result` will hold the integer value of the complement.

## Approach 3: High-Performance Bitmasking
The most efficient solution uses bitwise operations to compute the complement in constant time (for a fixed-size integer). The logic relies on the property that `num XOR mask = complement`, where the `mask` is a sequence of 1s with the same bit-length as `num`. The main task is to construct this mask efficiently.
**Time:** O(1). For a 32-bit integer, the number of operations is constant. Functions like `Integer.highestOneBit` are often implemented as hardware intrinsics, making them very fast. · **Space:** O(1). This approach uses a fixed number of variables, so its space usage is constant.
**Pros:** Extremely efficient, performing the calculation in constant time.; Uses constant space.; Elegant and concise for those familiar with bitwise operations.
**Cons:** The bit manipulation logic, especially for creating the mask, can be less intuitive for those not familiar with bitwise operations.
### Explanation
This approach finds the complement by first creating a bitmask. This mask has its bits set to 1 for all positions up to the most significant bit of the input number `num`. For example, if `num` is 5 (binary `101`), its bit-length is 3, so the required mask is `111` (decimal 7). Once this mask is obtained, the complement can be found simply by XORing the number with the mask (`num ^ mask`).

A highly efficient way to create this mask in Java is by using `Integer.highestOneBit(num)`. This function returns a value with only the single highest-order '1' bit from `num`. By shifting this value left by one and subtracting one, we get our desired mask.

```java
class Solution {
    public int findComplement(int num) {
        // Create a mask that has 1s up to the most significant bit of num.
        // For num = 5 (101), highestOneBit is 4 (100).
        // The mask becomes (4 << 1) - 1 = 7 (111).
        int mask = (Integer.highestOneBit(num) << 1) - 1;

        // The complement is num XORed with the mask.
        // 5 ^ 7 = (101) ^ (111) = 010 = 2.
        return num ^ mask;
    }
}
```
Alternatively, one could use the bitwise NOT operator `~` and the mask.
```java
class Solution {
    public int findComplement(int num) {
        int mask = (Integer.highestOneBit(num) << 1) - 1;
        
        // ~num flips all 32 bits. The mask is used to clear the leading bits.
        // ~5 is ...11111010. mask is ...00000111.
        // (~5) & mask = ...00000010 = 2.
        return ~num & mask;
    }
}
```
### Algorithm
- The key idea is that `num XOR mask = complement`, where `mask` is a number with the same bit-length as `num` but with all bits set to 1.
- **Step 1: Create the mask.** An efficient way to create this mask is needed.
  - Use `Integer.highestOneBit(num)` to get an integer with only the most significant bit of `num` set. For `num=5` (101), this gives 4 (100).
  - Create the full mask by shifting this value left by one and subtracting one: `mask = (Integer.highestOneBit(num) << 1) - 1`. For `num=5`, this is `(4 << 1) - 1 = 7` (111).
- **Step 2: Calculate the complement.**
  - Perform a bitwise XOR between `num` and the `mask`: `result = num ^ mask`.
- **Alternative Step 2:**
  - Flip all 32 bits of `num` using the NOT operator: `~num`.
  - Use the mask to turn off the unwanted leading 1s: `result = ~num & mask`.
- Return the result.

# Solutions
### Java

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

```

### JavaScript

```javascript
/** * @param {number} num * @return {number} */ var findComplement = function (
  num,
) {
  return num ^ (2 ** num.toString(2).length - 1);
};

```

### CPP

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

```

### Python

```python
class Solution:
    def findComplement(
        self, num: int) -> int: return num ^ (2 ** (len(bin(num)[2:])) - 1)

```