algoadvance

Given a positive integer num, output its complement number. The complement strategy is to flip the bits of its binary representation.

Example 1:

• Input: num = 5
• Output: 2
• Explanation: The binary representation of 5 is 101, and its complement is 010 which is the binary representation of 2.

Example 2:

• Input: num = 1
• Output: 0
• Explanation: The binary representation of 1 is 1, and its complement is 0.

Clarifying Questions

1. Q: What is the range of the input number num? A: The problem specifies that num is a positive integer, typically within the range of a standard 32-bit integer in many problems.

2. Q: Are there any constraints on the performance of the solution? A: Given that this is an interview problem, we should aim for an efficient solution, ideally O(n) where n is the number of bits in the number.

Strategy

1. Convert the number to binary: First, get the binary representation of the number.
2. Calculate the complement: Flip each bit in the binary string to get the complement.
3. Convert back to integer: Convert the resulting binary string back into an integer.

Code

def findComplement(num):
    # Find binary representation of the number without the '0b' prefix
    binary_rep = bin(num)[2:]
    
    # Find the complement by flipping each bit
    complement = ''.join('1' if bit == '0' else '0' for bit in binary_rep)
    
    # Convert the complement back to an integer
    return int(complement, 2)

# Test the function with the provided examples
print(findComplement(5))  # Output: 2
print(findComplement(1))  # Output: 0

Explanation

1. bin(num)[2:]: Converts the integer num to a binary string and slices off the ‘0b’ prefix to get a clean binary representation.
2. '1' if bit == '0' else '0' for bit in binary_rep: A generator expression that flips each bit in the binary string.
3. ''.join(...): Joins the flipped bits back into a single string.
4. int(complement, 2): Converts the binary string back to an integer.

Time Complexity

• Conversion to binary: O(n), where n is the number of bits.
• Flipping binary string: O(n), each bit is processed once.
• Converting back to integer: O(n), dependent on the number of digits in the binary string.

Overall, the time complexity of the solution is O(n).

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?