Jobs

Interviews

Discussions

Complement of Base 10 Integer

Easy

Asked by:

More companies

11 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 n, return its complement.

Example 1:

Input: n = 5
Output: 2
Explanation: 5 is "101" in binary, with complement "010" in binary, which is 2 in base-10.

Example 2:

Input: n = 7
Output: 0
Explanation: 7 is "111" in binary, with complement "000" in binary, which is 0 in base-10.

Example 3:

Input: n = 10
Output: 5
Explanation: 10 is "1010" in binary, with complement "0101" in binary, which is 5 in base-10.

Constraints:

0 <= n < 10⁹

Note: This question is the same as 476: https://leetcode.com/problems/number-complement/

Try coding it in LeetCode

Complement of Base 10 Integer

Easy

Asked by:

11 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 n, return its complement.

Example 1:

Input: n = 5
Output: 2
Explanation: 5 is "101" in binary, with complement "010" in binary, which is 2 in base-10.

Example 2:

Input: n = 7
Output: 0
Explanation: 7 is "111" in binary, with complement "000" in binary, which is 0 in base-10.

Example 3:

Input: n = 10
Output: 5
Explanation: 10 is "1010" in binary, with complement "0101" in binary, which is 5 in base-10.

Constraints:

0 <= n < 10⁹

Note: This question is the same as 476: https://leetcode.com/problems/number-complement/

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 range of possible values for the input integer n? Could it be negative or zero?
If n is zero, should the complement be zero, or should I treat it as a special case where the binary representation is effectively infinite leading zeros?
Are there any constraints on the size of the integer I can return, given the potential for bit flipping to significantly increase the value?
Is it safe to assume the input 'n' will always be a valid integer and not null or undefined?
Are we concerned about integer overflow when calculating the complement? If so, how should I handle it?

Brute Force Solution

Approach

The brute force way to find the complement involves trying every possible bit pattern until we find the one that, when combined with the original number, results in a power of two minus one. We achieve this by systematically testing potential complements.

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

First, find the smallest power of two that is bigger than the input number.
Start with zero as a potential complement.
Check if the input number plus the potential complement equals the power of two minus one.
If it does, you've found the complement; you're done!
If not, increase the potential complement by one.
Repeat steps 3-5 until you find the right complement.

Code Implementation

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

    potential_complement = 0
    while True:
        # Check if the potential complement is the correct one
        if number + potential_complement == power_of_two - 1:
            return potential_complement

        potential_complement += 1

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates to find the smallest power of two greater than the input number, num. In the worst-case scenario, the potential complement must iterate from 0 up to a value close to num itself. Thus, the loop checking potential complements executes a number of times proportional to the input number. Therefore, the time complexity is O(n), where n is approximately the value of the input number.

Space Complexity

O(1) – The described algorithm uses a fixed number of integer variables: one to store the smallest power of two greater than the input number, and another to hold the potential complement. Regardless of the input number N, the space required for these variables remains constant. There are no auxiliary data structures (like arrays, lists, or hash maps) used in this approach. Thus, the space complexity is O(1).

Optimal Solution

Approach

The goal is to flip all the bits of a number. A clever way to do this is to create a number with all bits set to 1 that's just large enough to cover all the bits in the original number, then subtract the original number from it.

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

First, find the smallest power of 2 that is bigger than the original number.
Next, subtract 1 from that power of 2. This creates a number where all the bits are 1, and the number is just big enough to cover all the bits in the original number.
Finally, subtract the original number from this 'all ones' number. The result will be the complement of the original number.

Code Implementation

def bitwiseComplement(number_to_complement):
    power_of_two = 1

    # Find the smallest power of 2 greater than the input number
    while power_of_two <= number_to_complement:
        power_of_two <<= 1

    # Subtract 1 to get a number with all bits set to 1
    all_bits_set = power_of_two - 1

    # XORing with all ones complements the bits
    complement = all_bits_set ^ number_to_complement
    return complement

Big(O) Analysis

Time Complexity

O(1) – The algorithm's runtime is not dependent on the magnitude of the input number n. Finding the smallest power of 2 greater than n involves a logarithmic operation with respect to n (number of bits to represent n), but since the number of bits is bounded by the size of integer which is a fixed size of bits (e.g., 32 or 64), we can treat finding the power of two as constant time. The subsequent subtraction operations are also constant time. Thus, the overall time complexity is O(1).

Space Complexity

O(1) – The algorithm calculates the complement using a power of 2, which is derived directly from the input number, and basic arithmetic operations. It doesn't create any auxiliary data structures that scale with the size of the input number N. Only a few integer variables are used for calculations, resulting in constant extra space regardless of the input size.

Edge Cases

Case	How to Handle
Input is 0	If n is 0, its binary representation is '0', the complement is '1', which is 1 in decimal, so return 1.
Input is 1	The binary rep is 1, complement is 0, return 0.
Integer Overflow	Check for integer overflow during the bit flipping and complement calculation by either using a larger data type like long, or by applying a modulo operation if the constraints define a maximum possible value.
Large Input (close to Integer.MAX_VALUE)	Ensure the intermediate binary representation or complement calculation doesn't exceed integer limits; consider using long or BigInteger if necessary and check memory usage.
Negative Input	The problem specifies a base-10 integer n, which is typically non-negative; clarify with the interviewer, and if negative numbers are permitted, handle 2's complement representation appropriately.
All bits are already 1	Handle the case when the binary representation is all 1s, ensuring correct complement is calculated (e.g., 7 becomes 0).
Leading zeros in binary representation	The algorithm must correctly identify the significant bits of the binary representation without being affected by leading zeros during the conversion to the complement.
Single bit set (e.g., power of 2)	Ensure the complement calculation functions properly when only one bit is set in the original number (e.g., 2 becomes 0, 4 becomes 3).

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 range of possible values for the input integer n? Could it be negative or zero?
If n is zero, should the complement be zero, or should I treat it as a special case where the binary representation is effectively infinite leading zeros?
Are there any constraints on the size of the integer I can return, given the potential for bit flipping to significantly increase the value?
Is it safe to assume the input 'n' will always be a valid integer and not null or undefined?
Are we concerned about integer overflow when calculating the complement? If so, how should I handle it?

Brute Force Solution

Approach

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

First, find the smallest power of two that is bigger than the input number.
Start with zero as a potential complement.
Check if the input number plus the potential complement equals the power of two minus one.
If it does, you've found the complement; you're done!
If not, increase the potential complement by one.
Repeat steps 3-5 until you find the right complement.

Code Implementation

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

    potential_complement = 0
    while True:
        # Check if the potential complement is the correct one
        if number + potential_complement == power_of_two - 1:
            return potential_complement

        potential_complement += 1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, find the smallest power of 2 that is bigger than the original number.
Next, subtract 1 from that power of 2. This creates a number where all the bits are 1, and the number is just big enough to cover all the bits in the original number.
Finally, subtract the original number from this 'all ones' number. The result will be the complement of the original number.

Code Implementation

def bitwiseComplement(number_to_complement):
    power_of_two = 1

    # Find the smallest power of 2 greater than the input number
    while power_of_two <= number_to_complement:
        power_of_two <<= 1

    # Subtract 1 to get a number with all bits set to 1
    all_bits_set = power_of_two - 1

    # XORing with all ones complements the bits
    complement = all_bits_set ^ number_to_complement
    return complement

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input is 0	If n is 0, its binary representation is '0', the complement is '1', which is 1 in decimal, so return 1.
Input is 1	The binary rep is 1, complement is 0, return 0.
Integer Overflow	Check for integer overflow during the bit flipping and complement calculation by either using a larger data type like long, or by applying a modulo operation if the constraints define a maximum possible value.
Large Input (close to Integer.MAX_VALUE)	Ensure the intermediate binary representation or complement calculation doesn't exceed integer limits; consider using long or BigInteger if necessary and check memory usage.
Negative Input	The problem specifies a base-10 integer n, which is typically non-negative; clarify with the interviewer, and if negative numbers are permitted, handle 2's complement representation appropriately.
All bits are already 1	Handle the case when the binary representation is all 1s, ensuring correct complement is calculated (e.g., 7 becomes 0).
Leading zeros in binary representation	The algorithm must correctly identify the significant bits of the binary representation without being affected by leading zeros during the conversion to the complement.
Single bit set (e.g., power of 2)	Ensure the complement calculation functions properly when only one bit is set in the original number (e.g., 2 becomes 0, 4 becomes 3).