LeetCode 1009 Complement of Base 10 Integer Explained | Bit Manipulation Easy Java Solution

In this tutorial we will understand LeetCode 1009: Complement of Base 10 Integer using a simple bit manipulation approach. We will go through the intuition, visual explanation, and Java implementation step by step.

---

Problem Statement

Given a non-negative integer n, return its bitwise complement.

The complement of a number is obtained by flipping every bit in its binary representation.

---

Step 1 – Convert Number to Binary

First convert the decimal number into binary.

---

Step 2 – Flip the Bits

Complement means flipping every bit.

---

Step 3 – Convert Back to Decimal

Final Answer = 2

---

Intuition Behind the Solution

Instead of manually flipping bits, we use a clever trick with XOR.

We create a mask of all 1s with the same number of bits as the given number.

Now perform XOR:

XOR automatically flips the bits.

---

Java Implementation

class Solution {

    public int bitwiseComplement(int n) {

        // Edge case
        if (n == 0) return 1;

        int mask = 0;
        int temp = n;

        // Create mask with all 1s
        while (temp > 0) {

            mask = (mask << 1) | 1;

            temp >>= 1;
        }

        // XOR to flip bits
        return n ^ mask;
    }
}

---

Code Explanation

Edge Case

if (n == 0) return 1;

Binary of 0 is 0. Flipping gives 1.

Create Mask

mask = (mask << 1) | 1;

This line builds a number like:

The mask becomes the same length as the binary number.

Flip Bits

return n ^ mask;

XOR flips bits because:

---

Complexity Analysis

Complexity	Value
Time Complexity	O(log n)
Space Complexity	O(1)

---

Other Possible Approaches

1. String Conversion Approach

Steps:

• Convert integer to binary string
• Flip characters
• Convert back to decimal

Pros

• Easy to understand

Cons

• Extra space
• Slower than bit manipulation

---

2. Bit-by-Bit Construction

Read each bit and build the complement manually. Pros

• Pure bit manipulation
• No string conversion

Cons

• More logic compared to XOR trick

---

Which Approach is Best?

Approach	Performance	Difficulty
XOR Mask	Fastest	Easy
Bit-by-Bit	Fast	Medium
String Method	Slow	Easy

---

Video Explanation

---

Conclusion

The key idea of this problem is understanding how to flip bits efficiently. Instead of manually processing every bit, we use a mask of 1s and perform an XOR operation.

This makes the solution elegant, fast, and perfect for coding interviews.

---