476. Number Complement - Detailed Explanation

Problem Statement

Given a positive integer, return its complement number. The complement is defined as the number you get when you flip all the bits in its binary representation. Only consider the bits up to the most significant 1.

Example 1

• Input: num = 5
• Explanation: The binary representation of 5 is 101. Flipping the bits results in 010, which is equal to 2.
• Output: 2

Example 2

• Input: num = 1
• Explanation: The binary representation of 1 is 1. Flipping the single bit gives 0.
• Output: 0

Example 3

• Input: num = 10
• Explanation: The binary representation of 10 is 1010. Flipping the bits results in 0101, which is equal to 5.
• Output: 5

Constraints:

• 1 ≤ num < 2³¹

Hints

1. Consider how you can generate a number that has all bits set to 1 up to the most significant bit of the given number. This “mask” can help you flip the bits with an XOR operation.
2. Explore how binary shifting operations can be used to build such a mask dynamically instead of working with string representations of binary numbers.

Approaches

Approach 1: Brute Force Using String Manipulation

Explanation

1. Convert to Binary String:
   Convert the number to its binary representation (as a string). For example, 5 becomes "101".
2. Flip Each Bit:
   Iterate through each character of the binary string and change '1' to '0' and '0' to '1'.
3. Convert Back to Decimal:
   Convert the resulting flipped binary string back to an integer.

Walkthrough with Example

For num = 5:

• Convert 5 to binary: "101".
• Flip each bit: "101" becomes "010".
• Convert "010" to a decimal: 2.

Complexity Analysis

• Time Complexity: O(b) where b is the number of bits in the binary representation.
• Space Complexity: O(b) for the binary string.

Pros and Cons

• Pros: Conceptually simple and easy to understand.
• Cons: Involves conversion between integer and string representations, which can be less efficient.

Approach 2: Optimal Bit Manipulation Using a Mask

Explanation

1. Determine the Mask:
   The idea is to create a mask that has all bits set to 1 in the position of the original number's binary representation. For an integer, you can generate such a mask by shifting left until the mask becomes greater than the number, then subtract 1.
   • For example, for num = 5:
     Start with mask = 1, then shift left until mask > 5:
     • mask = 1 (binary 001)
     • mask = 2 (binary 010)
     • mask = 4 (binary 100)
     • mask = 8 (binary 1000) → Now mask > 5
       Subtract 1 from mask: 8 - 1 = 7 (binary 111).
2. Compute the Complement:
   Use XOR (^) between the number and the mask to flip the bits.
   • For num = 5:
     5 (101) ^ 7 (111) = 2 (010).

Walkthrough with Example

For num = 10:

• Initial mask creation:
  • Start with mask = 1 (binary 0001).
  • Shift until mask > 10: mask becomes 2 (0010), then 4 (0100), then 8 (1000), and finally 16 (10000).
  • Subtract 1: 16 - 1 = 15 (binary 1111).
• Compute complement:
  • 10 (1010) ^ 15 (1111) = 5 (0101).

Complexity Analysis

• Time Complexity: O(b) where b is the number of bits in the number.
• Space Complexity: O(1) since only a few extra variables are used.

Pros and Cons

• Pros: More efficient; avoids conversion to and from strings.
• Cons: Requires a good understanding of bit manipulation and shifting operations.

Code Solutions

Python Implementation

Java Implementation

Step-by-Step Walkthrough and Visual Example

Let’s break down the optimal approach with num = 5 in detail:

1. Initial Number:
   5 in binary is represented as 101.

2. Constructing the Mask:

   • Start with mask = 1 (binary 001).
   • Shift left: mask becomes 2 (binary 010).
   • Shift left again: mask becomes 4 (binary 100).
   • Continue: mask becomes 8 (binary 1000); since 8 is now greater than 5, stop the loop.
   • Adjust the mask: subtract 1 from 8 → 7 (binary 111).

3. Computing the Complement:

   • Perform XOR between the original number (101) and the mask (111):

       101
     ^ 111
     ------
       010   (which is 2 in decimal)
     

4. Result:
   The complement of 5 is 2.

Common Mistakes

• Not Building the Correct Mask:
  A common error is to not shift the mask correctly or forgetting to subtract 1 at the end. Without subtracting 1, the mask will have a bit set higher than necessary.

• Incorrect Bitwise Operations:
  Using the wrong bitwise operator (e.g., using OR or AND instead of XOR) will not correctly flip the bits.

• Overlooking Edge Cases:
  Although the constraints guarantee num is at least 1, make sure to understand the behavior for numbers with a single-bit representation (like 1) and for numbers where all bits are already 1.

Edge Cases

• Single Bit Number:
  When num = 1, the binary is 1 and the complement is 0.
• Numbers with All Bits as 1:
  For numbers like num = 7 (binary 111), the mask will be 111 and their complement will be 0.

Alternative Variations of the Problem

• Find the Bitwise Complement of a Number with Different Bases:
  Instead of binary, you could be asked to perform similar operations in bases such as hexadecimal.

• Counting the Number of Bits to Flip:
  Another variation is to determine the number of bit flips required to convert one number to another, which is related to the Hamming distance problem.

• Related Problems:

  • Number of Steps to Reduce a Number in Binary Representation to One

  • Find Unique Binary String

  • Minimum Number of Changes to Make Binary String Beautiful