algoadvance

Leetcode 476. Number Complement

Problem Statement

The problem statement for Leetcode 476 - “Number Complement” is as follows:

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

For example:

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

Clarifying Questions

1. Q: What is the range of the input number num? A: The input number num is guaranteed to be a positive integer. We will assume it’s within the range typically constrained by a 32-bit signed integer, i.e., 1 <= num <= 2^31 - 1.

2. Q: Should the solution handle edge cases such as the smallest and largest numbers within the range? A: Yes, the solution should handle all positive integers within the range, including boundary values.

3. Q: Are there any constraints on the execution time or space complexity? A: Standard Leetcode constraints apply. We should aim for an efficient solution in terms of both time and space complexity.

Strategy

To solve this problem, we can follow these steps:

1. Convert the given number to its binary representation.
2. Create a mask which has the same number of bits as the binary representation of num but all bits set to 1. This can be achieved by shifting left and subtracting one.
3. XOR the original number with the mask to flip all bits.

Detailed steps:

1. Calculate the number of bits in num.
2. Generate a mask that has all these bits set to 1.
3. XOR num with this mask to get the complement.

Code

Here is the C++ code that efficiently computes the complement of a given number:

#include <iostream>
#include <cmath>
using namespace std;

class Solution {
public:
    int findComplement(int num) {
        if (num == 0) return 1;  // Special case for num = 0, though it's not a positive integer
        
        // Calculate the bit length of num
        int bitLength = log2(num) + 1;
        
        // Create a mask that has the same number of bits all set to 1
        int mask = (1 << bitLength) - 1;
        
        // XOR num with the mask to get the complement
        return num ^ mask;
    }
};

// Example usage:
int main() {
    Solution solution;
    int num = 5;  // Example number
    cout << "The complement of " << num << " is: " << solution.findComplement(num) << endl;
    return 0;
}

Time Complexity

• Time Complexity: The time complexity of this solution is O(1). This is because the number of operations performed (logarithm calculation for bit length and basic bit manipulations) are constant time relative to the size of an integer.
• Space Complexity: The space complexity is also O(1), as we are using a fixed number of additional variables.

This approach ensures that we have a minimal and efficient solution for finding the complement of a given positive integer.

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?