LeetCode Solution: 1009. Complement of Base 10 Integer

🤯 Unmasking the Magic: Cracking LeetCode 1009 with Bitwise Brilliance! ✨

Hey everyone! Vansh here, ready to dive into another exciting LeetCode challenge. Today, we're tackling a problem that might look simple on the surface but introduces some super cool bitwise operations that are fundamental to competitive programming and computer science in general.

Get ready to flip some bits and understand the magic behind 1009. Complement of Base 10 Integer!

---

What's the Problem All About? 🤔

Imagine you have a number, let's say 5. In the world of computers, this isn't just 5; it's a sequence of 0s and 1s – its binary representation. For 5, that's "101".

The problem asks us to find the complement of this number. What's a complement? It's simply what you get when you flip all the 0s to 1s and all the 1s to 0s in its binary form.

So, for 5 ("101"):

• The first 1 becomes 0.
• The 0 becomes 1.
• The last 1 becomes 0. Resulting in "010". If you convert "010" back to base 10, you get 2. And that's our answer for n=5!

Let's look at a couple more examples:

• Input: n = 7

  • Binary for 7 is "111".
  • Flipping all bits: "000".
  • "000" in base 10 is 0.
  • Output: 0

• Input: n = 10

  • Binary for 10 is "1010".
  • Flipping all bits: "0101".
  • "0101" in base 10 is 5.
  • Output: 5

Seems straightforward enough, right? Just flip the bits! But how do we actually do this in code, especially considering integers are usually stored in fixed-size memory (like 32-bit or 64-bit)? Let's find out!

---

The "Aha!" Moment: Our Core Intuition 💡

Our main goal is to flip bits. In most programming languages, there's a handy operator for this: the bitwise NOT (~) operator. If you apply ~ to a number, it flips every single bit in its binary representation.

However, there's a catch! If n=5 is "101", a 32-bit integer would actually be 00...00101. Applying ~ to this would turn it into 11...11010. This is a very large negative number, not 2! This is because ~ flips all 32 bits, including the leading zeros, turning them into ones.

We don't want to flip the leading zeros; we only care about the bits that make up the original number n. For n=5 ("101"), we only need to flip those three bits and ignore the rest.

So, the "aha!" moment is:

1. Flip all the bits of n using ~n.
2. Create a "mask" that has 1s only for the significant bits of n (i.e., the same number of bits as n). For n=5 ("101"), this mask would be "111".
3. Use the bitwise AND (&) operator to combine ~n with our mask. This will effectively "cut off" all the unwanted leading 1s from ~n, leaving us with just the flipped significant bits!

---

Step-by-Step Approach 🚀

Let's break down how we implement this intuition:

1. Handling the Edge Case: n = 0

The problem constraints state 0 <= n < 10^9. What happens if n = 0?

• Binary for 0 is "0".
• Flipping 0 gives 1.
• 1 in base 10 is 1. So, if n is 0, our answer is 1. We handle this separately to simplify the main logic, as 0 has no "leading zeros" in the conventional sense that our mask-building loop would usually define.

if (n == 0) {
    return 1;
}

2. Building the Mask (The Clever Part!):

This is where we figure out how many bits n has and create a mask of all 1s of that exact length.
Let's trace with n = 5 (binary 101):

• Initialize m = n (so we don't modify n) and mask = 0.
• We'll use a while loop that continues as long as m is not zero. Inside the loop, m will be right-shifted (>>1) to effectively remove its least significant bit in each iteration. This loop will run exactly as many times as there are bits in n.

| Iteration | m (binary) | mask (binary) | mask = (mask << 1) | 1 | m = m >> 1 | Notes |
| :-------: | :----------: | :-------------: | :------------------: | :----------: | :--------------------------------------------------------------------------------------: |
| Initial | 101 (5) | 0 (0) | | | |
| 1 | 101 (5) | 0 (0) | (0 << 1) | 1 = 0 | 1 = 1 (001) | 101 >> 1 = 010 (2) | mask is now 1. m has one less bit. |
| 2 | 010 (2) | 1 (1) | (1 << 1) | 1 = 2 | 1 = 3 (011) | 010 >> 1 = 001 (1) | mask is now 11. m has one less bit. |
| 3 | 001 (1) | 3 (3) | (3 << 1) | 1 = 6 | 1 = 7 (111) | 001 >> 1 = 000 (0) | mask is now 111. m has one less bit. |
| End Loop | 000 (0) | 7 (7) | | | m is 0, so the loop terminates. |

After the loop, our mask is 7 (binary 111), which is exactly what we need to cover all the bits of n = 5 (101)!

int m = n;
int mask = 0;
while (m != 0) {
    mask = (mask << 1) | 1; // Shift mask left and set LSB to 1
    m = m >> 1;             // Right shift m
}

3. Calculating the Final Answer:

Now that we have n and our perfect mask, we can get the complement:

int ans = (~n) & mask;

Let's break down (~n) & mask for n = 5:

• n = 5 (binary ...0000000000000000000000000000101 assuming 32-bit)
• ~n (bitwise NOT of n) = ...1111111111111111111111111111010
• mask = 7 (binary ...0000000000000000000000000000111)

Now, performing (~n) & mask:

   ...1111111111111111111111111111010  (~n)
&  ...0000000000000000000000000000111  (mask)
--------------------------------------
=  ...0000000000000000000000000000010  (ans)

The result ...0000000000000000000000000000010 is 2 in base 10! Exactly what we wanted! 🎉

---

The Complete Code 💻

class Solution {
public:
    int bitwiseComplement(int n) {
        // Edge case: if n is 0, its complement is 1.
        // Binary 0 -> Complement 1.
        if (n == 0) {
            return 1;
        }

        // 'm' is a temporary variable to count the bits in 'n'.
        // 'mask' will be built to have all 1s, matching the length of 'n'.
        int m = n;
        int mask = 0;

        // This loop determines the number of bits in 'n' and
        // constructs a 'mask' with all 1s up to that many bits.
        // Example: If n=5 (101), m will become 0 after 3 right shifts.
        // mask will become 1, then 11, then 111 (binary).
        while (m != 0) {
            // Left shift mask by 1 and set the least significant bit to 1.
            // This effectively appends a '1' to the right of the mask.
            mask = (mask << 1) | 1;
            // Right shift 'm' by 1, effectively removing its least significant bit.
            m = m >> 1;
        }

        // Now, 'mask' contains all 1s for the length of 'n'.
        // '~n' flips all bits of 'n' (including leading zeros).
        // '& mask' then zeroes out all the unwanted leading 1s that '~n' created,
        // leaving only the flipped significant bits of 'n'.
        int ans = (~n) & mask;

        return ans;
    }
};

---

Time & Space Complexity Analysis ⏳

• Time Complexity: O(log N)
  The while loop runs once for each bit in the binary representation of n. The number of bits required to represent an integer N is approximately log2(N). So, for n=5, it runs 3 times. For n=10^9, it runs about 30 times (log2(10^9) is approximately 29.89). This is very efficient!

• Space Complexity: O(1)
  We are only using a few extra integer variables (m, mask, ans), which consume a constant amount of memory regardless of the input n.

---

Key Takeaways ✨

• Bitwise Operators are Powerful: ~ (NOT), & (AND), | (OR), << (left shift), >> (right shift) are your best friends for low-level optimizations and certain types of problems.
• The Masking Technique: When dealing with fixed-size integer types (like int in C++), ~n will flip all bits. If you only want to operate on a specific range of bits, create a mask and use & to isolate those bits.
• Building a Mask: A common pattern to create a mask of k ones is to start with 0, and in a loop, repeatedly mask = (mask << 1) | 1. This incrementally builds 1, 11, 111, etc.
• Edge Cases Matter: Always think about 0 and other boundary conditions for bit manipulation problems.

This problem is a fantastic introduction to bitwise operations and a common pattern you'll encounter. Mastering these concepts will definitely give you an edge in competitive programming! Keep coding and happy flipping! 🥳

---

Vansh2710
Published: 2026-03-23 13:20:09