algoadvance

Leetcode 1009. Complement of Base 10 Integer

Problem Statement

Given a positive integer n, return its complement. 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 instance, given the input 5:

• The binary representation of 5 is 101.
• Flipping the bits, we get 010, which is 2 in decimal.

Thus, the output should be 2.

Clarifying Questions

1. Q: What should be the output if the input is 0?
   • A: If the input is 0, the binary representation is 0. The complement would be 1, as flipping 0 to 1 results in 1.
2. Q: Are there any constraints on the size of the integer n?
   • A: The problem statement typically ensures that n is a positive integer. However, for simplicity, we’ll assume n is a non-negative integer, consistent with typical constraints on such problems.
3. Q: Can the input integer be negative?
   • A: According to this problem definition, n is a positive integer, so we’ll not consider negative integers.

Strategy

1. Convert n to a binary string: We need to know the binary form of the number to perform the flipping.
2. Compute the bitwise complement: For each bit in the binary representation, flip 0 to 1 and 1 to 0.
3. Calculate the complement integer: Once we have the binary string of the complement, convert it back to a decimal integer.

To simplify, another approach is to use bitwise operations:

1. Determine the number of bits in n: Calculate the bit length.
2. Create a bitmask: A bitmask with all bits set to 1 for the length of the binary representation of n.
3. Apply the bitmask: Perform the bitwise XOR operation between n and the bitmask to get the complement.

Code

#include <iostream>
#include <cmath>

class Solution {
public:
    int bitwiseComplement(int n) {
        if (n == 0) {
            return 1;
        }
        
        // Determine the bit length of n.
        int bitLength = log2(n) + 1;
        
        // Create a mask with all bits set to 1, of the same length as n's binary representation.
        // For example, if bitLength is 3, mask will be `111` in binary which is `7` in decimal.
        int mask = (1 << bitLength) - 1;
        
        // Calculate the complement using XOR operation.
        return n ^ mask;
    }
};

int main() {
    Solution solution;
    int n;
    std::cout << "Enter a number: ";
    std::cin >> n;
    int result = solution.bitwiseComplement(n);
    std::cout << "The complement of " << n << " is " << result << std::endl;
    return 0;
}

Time Complexity

The time complexity of this solution is O(1).

• The log2(n) operation computes the bit length of the number, which is a constant time operation for any integer within the typical constraints.
• Bitwise operations such as bit shifts (<<), subtraction, and XOR (^) operate in constant time as they are performed directly on binary representations of fixed-width integers.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?