algoadvance

Leetcode 1009. Complement of Base 10 Integer

Problem Statement

Leetcode Problem 1009: Complement of Base 10 Integer

Given a positive integer n, you need to find the complement of its binary representation. The complement strategy is to flip the bits of its binary representation.

Example 1:

Example 2:

Clarifying Questions

  1. Is the input always a non-negative integer?
    • Yes, the input is guaranteed to be a non-negative integer.
  2. What should be returned if the input is 0?
    • The complement of 0 is 1, according to the description of bit flipping.
  3. Are there any constraints on the size of n?
    • Typically, n will be within the bounds of a 32-bit signed integer.

Strategy

  1. Find the Binary Representation: Convert the integer n into its binary form.
  2. Generate Full Binary Mask: Create a mask with all bits set based on the length of the binary representation of n.
  3. Compute the Complement: XOR the integer with this mask to flip all the bits.
  4. Return the Result: Convert the result back to a base-10 integer if needed (in Java, this will already be a base-10 integer).

Step-by-Step Plan

  1. Determine the length of the binary representation of n.
  2. Compute a mask with all bits set to 1 for the length of the binary representation.
  3. Use the XOR operator to flip the bits.
  4. Output the decimal representation of the result.

Code

public class ComplementBase10Integer {
    public int bitwiseComplement(int n) {
        // Edge case: when n is 0, the complement is 1
        if (n == 0) return 1;
        
        // Determine the bit length of n
        int bitLength = Integer.toBinaryString(n).length();
        
        // Create a mask of the same length with all bits set to 1
        int mask = (1 << bitLength) - 1;
        
        // XOR n with the mask to get the complement
        int complement = n ^ mask;
        
        return complement;
    }

    public static void main(String[] args) {
        ComplementBase10Integer solution = new ComplementBase10Integer();
        
        System.out.println(solution.bitwiseComplement(5));  // Output: 2
        System.out.println(solution.bitwiseComplement(1));  // Output: 0
        System.out.println(solution.bitwiseComplement(0));  // Output: 1
    }
}

Time Complexity

The time complexity of this solution is O(1) because:

  1. The operations to find the length of the binary string and create the bit mask are constant-time operations.
  2. XOR operation is also a constant-time operation.

Therefore, the overall time complexity is O(1).

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