1009. Complement of Base 10 Integer

EasyBit Manipulation
Leetcode Link

Problem Description

The problem requires us to determine the complement of a given integer n. The complement operation flips every bit in the binary representation of the number, which means that each '1' changes to '0' and each '0' to '1'. This is similar to finding the bitwise NOT operation in most programming languages, but with a caveat: we only flip the bits up to the most significant '1' in the original number and ignore all leading '0's. For example, if n has the binary representation of '101', it has leading '0's that are not represented like '00000101'. After flipping the bits, the complement would be '010'.

The challenge lies in finding an efficient way to perform this task programmatically without manually converting the number to its binary string representation and back. Also, we have to ensure that we are not including any leading '0's that might appear if the number were represented using a fixed number of bits (like 32 bits in many computer systems).

Intuition

The solution to this problem uses bitwise operations to find the complement without converting the number to a binary string. The intuition comes from observing how binary numbers work and utilizing bit manipulation to find the complement:

  • We iterate over the bits of integer n, starting from the most significant bit (MSB) to the least significant bit (LSB). In a 32-bit integer, the MSB would be at position 31 (0-indexed).
  • We need to find where the first '1' bit from the left (MSB) is located in n, skipping all leading '0's.
  • Once the first '1' bit is encountered, each subsequent '0' bit in n becomes '1' in the answer, and each '1' bit in n does not contribute to the answer (remains '0').
  • The algorithm creates an initial ans variable of 0 and starts flipping the bits of ans when the first '1' is found in n.
  • Bitwise AND (&) operation is used to test the bit at each position (1 << i). If the bit is '0', then we bitwise OR (|) the ans with 1 << i to set the corresponding bit to '1'.

The code effectively loops through the bits of n using a for loop that checks 31 bits (adjust this according to the size of the integers you're working with). It uses two flags: find to mark that we've found the first '1' bit and should start flipping bits, and b to hold the result of the bitwise AND operation for the current bit. If find is True, and b is 0, the ans variable is updated using bitwise OR with 1 << i to flip the current bit to '1'. If n is 0, it's a special case, and the complement would be 1.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Solution Approach

To implement the solution to find the complement of an integer, the following steps are taken using bit manipulation techniques:

  1. First, we handle the edge case where n is 0. Since the binary representation of 0 is just '0' and its complement is '1', we immediately return 1 without further processing.

  2. Then, we initialize an answer variable ans to 0. This variable will accumulate the result bit by bit.

  3. The variable find is initialized to False. This boolean flag will indicate when we've encountered the first '1' bit from the left in the binary representation of n. We do not want to flip any leading '0's, so we should start flipping bits only after find is set to True.

  4. We then iterate through the potential bit positions of n using a for loop with the range 30 down to 0, which covers up to 31 bits for a non-negative integer in a 32-bit system. The loop index i represents the bit position we're checking, starting from the most significant bit.

  5. Inside the loop, the bitwise AND operation b = n & (1 << i) checks if the bit at position i in n is a '1'. The expression 1 << i creates a number with a single '1' bit at the i-th position and '0's elsewhere.

  6. If find is False and b is 0, that means we are still encountering leading '0's, so we continue to the next iteration without changing ans.

  7. Once we find the first '1' (when b is not 0), we set find to True to indicate that we should start flipping bits.

  8. Thereafter, for every position i where b is 0 (indicating the bit in n was '0'), we flip the bit to '1' in ans by performing the bitwise OR operation ans |= 1 << i.

The use of bitwise operations makes this solution very efficient, as no string conversion or arithmetic operations with potentially large numbers are required. The core algorithm iterates through the bits of the number once, making it run in O(1) time with respect to the size of the integer (since the number of bits is constant for a standard integer size) and O(1) space because it only uses a fixed number of extra variables.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Example Walkthrough

Let's illustrate the solution approach with a small example. Assume our input number n is 5, which has a binary representation of '101'.

  1. First, we check if n is 0. If it were 0, we would return 1. But since n is 5, we move to the next step.

  2. We initialize the answer variable ans to 0. This will hold the result of the complemented bits.

  3. We set our flag find to False as we have not yet encountered the first '1' from the left.

  4. We then loop from 30 down to 0. For simplicity in this example, we will only loop from 2 down to 0 because 5 is a small number and only needs 3 bits to represent it in binary.

  5. During each iteration, we use the bitwise AND operation b = n & (1 << i) to test if the current bit is '1'.

    • On the first iteration (i = 2), b = 5 & (1 << 2) which is 5 & 4 or 101 & 100 in binary, which equals 100. Since b is not 0, we set find to True.

  6. Subsequent iterations will now flip bits after the most significant '1' has been found.

  7. On the second iteration (i = 1), b = 5 & (1 << 1) which is 5 & 2 or 101 & 010 in binary, which equals 0. Since find is True and b is 0, we flip the i-th bit of ans: ans |= 1 << 1. Now, ans = 0 | 010, so ans is now 2 in decimal.

  8. On the last iteration (i = 0), b = 5 & (1 << 0) which is 5 & 1 or 101 & 001 in binary, which equals 1. There is no flipping since b is not 0.

Therefore, the binary complement of '101' (the binary representation of 5) is '010', which in decimal is 2. The final output of the complement of 5 is 2.

Solution Implementation

1class Solution:
2    def bitwiseComplement(self, N: int) -> int:
3        # If the input is 0, we know the bitwise complement is 1
4        if N == 0:
5            return 1
6      
7        # Initialize the answer to 0
8        answer = 0
9        # This variable is to determine when to start flipping bits
10        found_first_one = False
11      
12        # Iterate through 31 bits of the integer to include the case of a 32-bit integer
13        for i in range(31, -1, -1):
14            # Check if the bit at the ith position is set (1)
15            bit_is_set = N & (1 << i)
16          
17            # Skip leading zeros until we find the first set bit
18            if not found_first_one and bit_is_set == 0:
19                continue
20          
21            # The first set bit is found
22            found_first_one = True
23            # If the current bit is 0, set the corresponding bit in the answer
24            if bit_is_set == 0:
25                answer |= 1 << i
26      
27        # Return the computed bitwise complement
28        return answer
29
1class Solution {
2    // Method that calculates the bitwise complement of a given integer 'n'
3    public int bitwiseComplement(int n) {
4        // Check for the base case where n is 0,
5        // the bitwise complement of 0 is 1.
6        if (n == 0) {
7            return 1;
8        }
9        // Initialize answer to 0
10        int answer = 0;
11        // A flag to indicate when the first non-zero bit from the left is found
12        boolean foundFirstNonZeroBit = false;
13        // Iterate from the 30th bit to the 0th bit, 
14        // because an integer in Java has 31 bits for the integer value
15        // and 1 bit for the sign.
16        for (int i = 30; i >= 0; --i) {
17            // Check if i-th bit in n is set
18            int bit = n & (1 << i);
19            // Ignore leading zeroes in n,
20            // we do not want to take them into the complement calculation.
21            if (!foundFirstNonZeroBit && bit == 0) {
22                continue;
23            }
24            // Once the first non-zero bit is found, we set the flag to true
25            foundFirstNonZeroBit = true;
26            // If the current bit is 0, its complement is 1,
27            // and we set the corresponding bit in the answer.
28            if (bit == 0) {
29                answer |= (1 << i);
30            }
31            // Note: There is no need to explicitly handle the case when the bit is 1,
32            // because its complement is 0 and the answer is already initialized to 0.
33        }
34        // Return the computed bitwise complement of n
35        return answer;
36    }
37}
38
1class Solution {
2public:
3    int bitwiseComplement(int n) {
4        if (n == 0) {
5            // The complement of 0 is 1, as all bits are flipped.
6            return 1;
7        }
8
9        int result = 0; // This will hold the result of the complement.
10        bool foundOne = false; // Flag to check if a '1' bit has been found.
11
12        // Loop through the bits of the integer, starting from the most significant bit (MSB).
13        for (int i = 30; i >= 0; --i) {
14            int bit = n & (1 << i); // Get the i-th bit.
15
16            // Skip the leading zeroes to find the first '1'.
17            if (!foundOne && bit == 0) continue;
18
19            // Mark that we have found the first '1', so we include the rest of the bits.
20            foundOne = true;
21          
22            // If the current bit is '0', flip it to '1' in the result.
23            if (bit == 0) {
24                result |= (1 << i);
25            }
26            // Otherwise, the bit is '1' and the result remains '0' (implicitly flipped to '0').
27        }
28
29        // Return the bitwise complement of the original number.
30        return result;
31    }
32};
33
1function bitwiseComplement(n: number): number {
2    if (n === 0) {
3        // The complement of 0 is 1, as all bits are flipped.
4        return 1;
5    }
6
7    let result: number = 0; // This will hold the result of the complement.
8    let foundOne: boolean = false; // Flag to check if a '1' bit has been found.
9
10    // Loop through the bits of the integer, starting from the most significant bit (MSB).
11    for (let i: number = 30; i >= 0; --i) {
12        let bit: number = n & (1 << i); // Get the i-th bit.
13
14        // Skip the leading zeroes to find the first '1'.
15        if (!foundOne && bit === 0) continue;
16
17        // Mark that we have found the first '1', so we include the rest of the bits.
18        foundOne = true;
19
20        // If the current bit is '0', flip it to '1' in the result.
21        if (bit === 0) {
22            result |= (1 << i);
23        }
24        // Otherwise, the bit is '1' and the result remains '0' (implicitly flipped to '0').
25    }
26
27    // Return the bitwise complement of the original number.
28    return result;
29}
30
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Time and Space Complexity

The time complexity of the given code is O(1) because the loop runs for a maximum of 31 iterations (since the loop is from i = 30 to i = -1), which is a constant time operation irrespective of the input size n.

The space complexity of the code is also O(1), as there's a fixed and limited amount of extra space being used (variables ans, find, b, and constant space for i). No additional space that scales with input size n is being utilized.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫