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

Number Complement

Number: 476

Difficulty: Easy

Paid? No

Companies: Cloudera

Problem Description

Given a positive integer num, return its complement. The complement is produced by flipping all the bits in the binary representation of num (changing 0s to 1s and 1s to 0s), ignoring any leading zeros.

Key Insights

  • Determine the number of bits in num (its binary length).
  • Generate a mask with all bits set to 1 for that length.
  • XOR num with the mask to produce the complement.
  • This solution leverages bit manipulation for an efficient computation.

Space and Time Complexity

Time Complexity: O(n) (where n is the number of bits in num)
Space Complexity: O(1)

Solution

The approach begins by calculating the number of bits in the binary representation of num. Next, a mask is constructed where all bits are set to 1 for that bit-length. By XORing the original number with the mask, we flip each bit of num. This method capitalizes on efficient bitwise operations to solve the problem.

Code Solutions

# Python solution for the Number Complement problem

def find_complement(num):
    # Determine the number of bits in the binary representation of num
    num_bits = num.bit_length()  # Example: 5 -> '101' has 3 bits
    
    # Create a mask with all 1s for the number of bits (e.g., for 3 bits, mask = 0b111)
    mask = (1 << num_bits) - 1
    
    # XOR num with mask to flip its bits and obtain the complement
    complement = num ^ mask
    return complement

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