Jobs

Interviews

Discussions

Number Complement

#2 Most AskedEasy

Number Complement #2 Most Asked

Easy

Cloudera

5 views

Topics:

Bit Manipulation

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 < 2³¹

Note: This question is the same as 1009: https://leetcode.com/problems/complement-of-base-10-integer/

Try coding it in LeetCode

Number Complement

#2 Most AskedEasy

Number Complement #2 Most Asked

Easy

Cloudera

5 views

Topics:

Bit Manipulation

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 < 2³¹

Note: This question is the same as 1009: https://leetcode.com/problems/complement-of-base-10-integer/

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible value of the input integer 'num'?
Are we guaranteed that the input 'num' will always be a positive integer?
Could you clarify what should be returned if the input is, for some reason, outside the expected positive integer range?
By 'flip the bits', do you mean flipping all bits up to the most significant bit of the number, or considering a fixed bit width, like 32-bits?
Are we optimizing for space, or is minimizing code complexity the priority?

Brute Force Solution

Approach

The brute force method for finding the number complement involves checking all possible numbers to find the correct one. We will systematically try each potential complement until we identify the number that, when added to the original number, results in a power of two minus one.

Here's how the algorithm would work step-by-step:

First, determine the smallest power of two that is greater than the input number.
Calculate one less than this power of two. This represents the maximum value the combination of the input and its complement could be.
Now, start from zero and try every number less than or equal to the maximum value we just calculated.
For each number, add it to the original input number.
If the sum equals the maximum value (power of two minus one), then that number is the complement.
If you go through all the numbers and none of them work, it means there's an error in the initial calculation, but for this problem, that won't happen.

Code Implementation

def number_complement_brute_force(number):
    power_of_two = 1
    # Find the smallest power of 2 greater than the number
    while power_of_two <= number:
        power_of_two *= 2

    max_value = power_of_two - 1

    # Iterate through possible complements
    for possible_complement in range(max_value + 1):

        # Check if current number is the complement
        if number + possible_complement == max_value:
            return possible_complement

Big(O) Analysis

Time Complexity

O(n) – The algorithm's runtime is determined by the loop that iterates to find the complement. The number of iterations in this loop is bounded by the smallest power of two greater than the input number, which we can represent as 2^k. Since 2^k will be greater than n, the number itself, and the loop iterates up to 2^k - 1, in the worst case the number of iterations is linearly proportional to n. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The provided algorithm calculates a power of two and stores it in a variable. It then iterates through numbers and stores the current number being tested as a potential complement. Only a few integer variables are used to store intermediate calculations such as the power of two, the maximum value (power of two minus one), and the current complement candidate. The space required for these variables remains constant regardless of the input number. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

To find the complement of a number, we want to flip all of its bits (0s become 1s and 1s become 0s). The trick is to create a mask of all 1s that's the same length as the original number's binary representation and then use that mask to flip the bits.

Here's how the algorithm would work step-by-step:

First, figure out how many bits are in the original number's binary form. Think of it as figuring out how many digits are needed to write the number in base 2.
Next, create a number that has the same number of bits as the original number, but with all bits set to 1. This is our mask. For example, if the original number has 3 bits, the mask would be 111 in binary (which is 7 in decimal).
Finally, perform a bitwise XOR operation between the original number and the mask. This will flip all the bits in the original number, giving you the complement.

Code Implementation

def find_complement(number): 
    # Find the number of bits
    number_of_bits = 0
    temp_number = number
    while temp_number > 0:
        temp_number >>= 1
        number_of_bits += 1

    # Construct a mask with all bits set to 1
    # The mask should have the same number of bits as the input number
    mask = (1 << number_of_bits) - 1

    # XOR operation flips the bits and gives us the complement
    complement = number ^ mask

    return complement

Big(O) Analysis

Time Complexity

O(1) – The time complexity is determined by the number of bits in the input number 'num'. The algorithm first calculates the number of bits, which takes logarithmic time with respect to the input number, but since integer sizes are fixed (e.g., 32 bits or 64 bits), this operation has a maximum bound. Constructing the mask and performing the XOR operation are constant time operations. Therefore, the overall time complexity is O(1) because it is bound by the fixed size of integers and not dependent on an arbitrarily large input size.

Space Complexity

O(1) – The algorithm computes the number of bits required to represent the input number and then calculates a mask. These computations and the mask itself are stored in variables. The space required for these variables is constant and does not depend on the size of the input number, N. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Input number is 1	The binary representation is '1', flipping it results in '0', so return 0.
Input number is the maximum integer value (2^31 - 1 or 2^63-1 depending on the language)	Handle potential overflow when calculating the mask by using a wider integer type if available or by iterative shifting.
Input is 0 (while the problem specifies positive, robustness is good)	Return 0 immediately if input is 0; some definitions might see the complement of 0 as 0.
Large number with many leading zeros after flipping	The mask calculation correctly identifies the number of significant bits, eliminating the need for post-processing to trim leading zeros.
Number is a power of 2 minus 1 (e.g., 3, 7, 15)	The complement should be zero, and the bit manipulation handles this correctly because all bits are 1 initially.
Negative input (invalid according to problem description, but good to check)	Throw an exception or return an error code to indicate invalid input, as negative numbers are not valid inputs according to the problem statement.
Input is a very large power of 2	Ensure the bit mask calculation handles very large powers of 2 without overflowing, using appropriate bitwise operations and data types to accommodate the number of bits.
Language-specific integer size limits cause unexpected behavior	Use unsigned integers if available to avoid issues with sign bits and represent the number in its pure binary form without sign complications.

Input number is 1

How to Handle:

The binary representation is '1', flipping it results in '0', so return 0.

Input number is the maximum integer value (2^31 - 1 or 2^63-1 depending on the language)

How to Handle:

Handle potential overflow when calculating the mask by using a wider integer type if available or by iterative shifting.

Input is 0 (while the problem specifies positive, robustness is good)

How to Handle:

Return 0 immediately if input is 0; some definitions might see the complement of 0 as 0.

Large number with many leading zeros after flipping

How to Handle:

The mask calculation correctly identifies the number of significant bits, eliminating the need for post-processing to trim leading zeros.

Number is a power of 2 minus 1 (e.g., 3, 7, 15)

How to Handle:

The complement should be zero, and the bit manipulation handles this correctly because all bits are 1 initially.

Negative input (invalid according to problem description, but good to check)

How to Handle:

Throw an exception or return an error code to indicate invalid input, as negative numbers are not valid inputs according to the problem statement.

Input is a very large power of 2

How to Handle:

Ensure the bit mask calculation handles very large powers of 2 without overflowing, using appropriate bitwise operations and data types to accommodate the number of bits.

Language-specific integer size limits cause unexpected behavior

How to Handle:

Use unsigned integers if available to avoid issues with sign bits and represent the number in its pure binary form without sign complications.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible value of the input integer 'num'?
Are we guaranteed that the input 'num' will always be a positive integer?
Could you clarify what should be returned if the input is, for some reason, outside the expected positive integer range?
By 'flip the bits', do you mean flipping all bits up to the most significant bit of the number, or considering a fixed bit width, like 32-bits?
Are we optimizing for space, or is minimizing code complexity the priority?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, determine the smallest power of two that is greater than the input number.
Calculate one less than this power of two. This represents the maximum value the combination of the input and its complement could be.
Now, start from zero and try every number less than or equal to the maximum value we just calculated.
For each number, add it to the original input number.
If the sum equals the maximum value (power of two minus one), then that number is the complement.
If you go through all the numbers and none of them work, it means there's an error in the initial calculation, but for this problem, that won't happen.

Code Implementation

def number_complement_brute_force(number):
    power_of_two = 1
    # Find the smallest power of 2 greater than the number
    while power_of_two <= number:
        power_of_two *= 2

    max_value = power_of_two - 1

    # Iterate through possible complements
    for possible_complement in range(max_value + 1):

        # Check if current number is the complement
        if number + possible_complement == max_value:
            return possible_complement

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, figure out how many bits are in the original number's binary form. Think of it as figuring out how many digits are needed to write the number in base 2.
Next, create a number that has the same number of bits as the original number, but with all bits set to 1. This is our mask. For example, if the original number has 3 bits, the mask would be 111 in binary (which is 7 in decimal).
Finally, perform a bitwise XOR operation between the original number and the mask. This will flip all the bits in the original number, giving you the complement.

Code Implementation

def find_complement(number): 
    # Find the number of bits
    number_of_bits = 0
    temp_number = number
    while temp_number > 0:
        temp_number >>= 1
        number_of_bits += 1

    # Construct a mask with all bits set to 1
    # The mask should have the same number of bits as the input number
    mask = (1 << number_of_bits) - 1

    # XOR operation flips the bits and gives us the complement
    complement = number ^ mask

    return complement

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input number is 1	The binary representation is '1', flipping it results in '0', so return 0.
Input number is the maximum integer value (2^31 - 1 or 2^63-1 depending on the language)	Handle potential overflow when calculating the mask by using a wider integer type if available or by iterative shifting.
Input is 0 (while the problem specifies positive, robustness is good)	Return 0 immediately if input is 0; some definitions might see the complement of 0 as 0.
Large number with many leading zeros after flipping	The mask calculation correctly identifies the number of significant bits, eliminating the need for post-processing to trim leading zeros.
Number is a power of 2 minus 1 (e.g., 3, 7, 15)	The complement should be zero, and the bit manipulation handles this correctly because all bits are 1 initially.
Negative input (invalid according to problem description, but good to check)	Throw an exception or return an error code to indicate invalid input, as negative numbers are not valid inputs according to the problem statement.
Input is a very large power of 2	Ensure the bit mask calculation handles very large powers of 2 without overflowing, using appropriate bitwise operations and data types to accommodate the number of bits.
Language-specific integer size limits cause unexpected behavior	Use unsigned integers if available to avoid issues with sign bits and represent the number in its pure binary form without sign complications.

Input number is 1

How to Handle:

The binary representation is '1', flipping it results in '0', so return 0.

Input number is the maximum integer value (2^31 - 1 or 2^63-1 depending on the language)

How to Handle:

Handle potential overflow when calculating the mask by using a wider integer type if available or by iterative shifting.

Input is 0 (while the problem specifies positive, robustness is good)

How to Handle:

Return 0 immediately if input is 0; some definitions might see the complement of 0 as 0.

Large number with many leading zeros after flipping

How to Handle:

The mask calculation correctly identifies the number of significant bits, eliminating the need for post-processing to trim leading zeros.

Number is a power of 2 minus 1 (e.g., 3, 7, 15)

How to Handle:

The complement should be zero, and the bit manipulation handles this correctly because all bits are 1 initially.

Negative input (invalid according to problem description, but good to check)

How to Handle:

Throw an exception or return an error code to indicate invalid input, as negative numbers are not valid inputs according to the problem statement.

Input is a very large power of 2

How to Handle:

Ensure the bit mask calculation handles very large powers of 2 without overflowing, using appropriate bitwise operations and data types to accommodate the number of bits.

Language-specific integer size limits cause unexpected behavior

How to Handle:

Use unsigned integers if available to avoid issues with sign bits and represent the number in its pure binary form without sign complications.

0/5 Cloudera questions completed

0/5 completed