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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Complement of Base 10 Integer

Number: 1054

Difficulty: Easy

Paid? No

Companies: Bloomberg, Adobe, Amazon, Apple, Google, Uber, Cloudera

Problem Description

Given an integer n, return its complement. The complement of an integer is obtained by flipping all bits in its binary representation (changing 0s to 1s and 1s to 0s).

Key Insights

  • Convert the integer to its binary form.
  • Determine a mask that covers all bits in n (mask will have all bits set to 1 for the length of n in binary).
  • Use the XOR operation between n and the mask to flip the bits.
  • Handle the edge case when n equals 0.

Space and Time Complexity

Time Complexity: O(1) (the number of iterations is bounded by the number of bits of n) Space Complexity: O(1)

Solution

The approach starts by creating a mask that has all bits set to 1 corresponding to the bit-length of n. This is done by continuously left shifting a mask starting from 1 until it exceeds n, then subtracting 1 to fill in all lower bits with 1s. Finally, an XOR of n with this mask flips the bits of n, resulting in its complement.

Code Solutions

# Python solution with line-by-line comments

def findComplement(n):
    # Edge case: if n is 0, its complement is 1.
    if n == 0:
        return 1
    # Initialize mask with the value 1.
    mask = 1
    # Left shift the mask until it becomes greater than n.
    # This builds a mask that is just larger than n.
    while mask <= n:
        mask = mask << 1
    # Subtract 1 to get a mask with all bits set to 1 for the bit-length of n.
    mask -= 1
    # XOR n with mask to flip all bits and return the complement.
    return n ^ mask

# Example usage:
print(findComplement(5))  # Output: 2
← Back to All Questions