algoadvance

Leetcode 476. Number Complement

Problem Statement:

Given a positive integer num, output its complement number. The complement strategy is to flip the bits of its binary representation. For instance, the binary complement of the number 5 (101 in binary) is 2 (010 in binary).

Example 1:

Input: num = 5
Output: 2
Explanation: The binary representation of 5 is 101 (5 in decimal), and its complement is 010 (2 in decimal).

Example 2:

Input: num = 1
Output: 0
Explanation: The binary representation of 1 is 1 (1 in decimal), and its complement is 0 (0 in decimal).

Constraints:

• The given integer num is guaranteed to fit within the range of a 32-bit signed integer.
• num >= 1

Clarifying Questions:

1. Q: What is the maximum value of the input number?
   • A: The maximum value is (2^{31} - 1) (the limit for a 32-bit signed integer).
2. Q: Are there any special requirements for the output format?
   • A: The output should be an integer which is the complement of the given number.
3. Q: Do we need to handle negative values?
   • A: No, the problem constraints ensure the input will always be a positive integer.

Strategy:

1. Convert the number to its binary representation.
2. Create a mask which has all bits set to 1 up to the most significant bit in the binary representation of the number.
3. XOR the original number with this mask to flip all bits.

Detailed Steps:

1. Calculate the bit length of num.
2. Create a mask of the same bit length with all bits set to 1.
3. XOR the number with the mask to get the complement.

Code:

public class NumberComplement {
    public int findComplement(int num) {
        // Calculate the bit length of num
        int bitLength = (int)(Math.log(num) / Math.log(2)) + 1;
        
        // Create a mask with all 1s of the same bit length as num
        int mask = (1 << bitLength) - 1;
        
        // XOR num with the mask to get the complement
        return num ^ mask;
    }

    public static void main(String[] args) {
        NumberComplement nc = new NumberComplement();
        
        // Test cases
        System.out.println(nc.findComplement(5)); // Output: 2
        System.out.println(nc.findComplement(1)); // Output: 0
    }
}

Time Complexity:

• Time Complexity: The time complexity is (O(1)) because the number of operations required does not depend on the input size. The logarithmic operation and bit manipulation are performed in constant time.
• Space Complexity: The space complexity is also (O(1)), since we are using a constant amount of space regardless of the input size.

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?