We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number Complement

Difficulty: Easy

Problem Description

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. Given an integer num, return its complement.

Key Insights

  • The complement of a number can be found by flipping its binary representation.
  • The binary representation of a number can be computed using bit manipulation.
  • The complement can be efficiently calculated using the XOR operation with a mask.

Space and Time Complexity

Time Complexity: O(log(num)), where log(num) is the number of bits in the binary representation of the number. Space Complexity: O(1), as we are using a constant amount of space regardless of the input size.

Solution

To find the complement of a number, we can use the following approach:

  1. Determine the number of bits required to represent the number in binary.
  2. Create a mask with all bits set to 1 for the same number of bits.
  3. Use the XOR operation between the original number and the mask to flip the bits.

This approach uses bit manipulation, specifically the XOR operation, which efficiently computes the result without needing to convert to and from binary strings.

Code Solutions

def findComplement(num: int) -> int:
    # Determine the number of bits in num
    mask = 1
    while mask <= num:
        mask <<= 1  # Shift left to create a mask of all 1's
    mask -= 1  # Subtract 1 to get the mask with all bits set to 1
    return num ^ mask  # XOR num with mask to get the complement
← Back to All Questions