algoadvance

Leetcode 869. Reordered Power of 2

Problem Statement

You are given an integer n. Reorder the digits of n (in any order) such that the resulting number is a power of two. Return true if possible, otherwise return false.

Clarifying Questions

1. Will n be a non-negative integer for sure?
   • Yes, n will be a non-negative integer as per the problem’s context.
2. What is the expected range of the input integer n?
   • The constraints are not explicitly provided, but typically n is within the range of a 32-bit signed integer in problems like these (0 to 2,147,483,647).
3. Can n have leading zeroes after reordering its digits?
   • No, leading zeroes are not allowed in the resulting number.

Strategy

1. Generate All Powers of 2:
   • First, generate all possible powers of 2 that are within the 32-bit integer limit.
2. Sort the Digits:
   • For any given power of 2, sort its digits and store them in a set.
   • Similarly, sort the digits of n.
3. Comparison:
   • Check if the sorted digit sequence of n matches with any of the sorted sequences in the set of powers of 2.

Code

import java.util.HashSet;
import java.util.Set;
import java.util.Arrays;

public class ReorderedPowerOf2 {
    // Function to determine if the number can be reordered to form a power of two
    public boolean reorderedPowerOf2(int n) {
        // Generate all powers of 2 within the range of 32-bit integers
        Set<String> powerOf2Digits = new HashSet<>();
        for (int i = 0; i < 31; i++) {
            int powerOf2 = 1 << i;
            char[] powerDigits = Integer.toString(powerOf2).toCharArray();
            Arrays.sort(powerDigits);
            powerOf2Digits.add(new String(powerDigits));
        }

        // Sort the digits of the input number
        char[] numberDigits = Integer.toString(n).toCharArray();
        Arrays.sort(numberDigits);
        String sortedNumberDigits = new String(numberDigits);

        // Check if the sorted input number digits match any of the power of 2 sorted digits
        return powerOf2Digits.contains(sortedNumberDigits);
    }

    public static void main(String[] args) {
        ReorderedPowerOf2 solution = new ReorderedPowerOf2();
        System.out.println(solution.reorderedPowerOf2(128));  // True
        System.out.println(solution.reorderedPowerOf2(256));  // True
        System.out.println(solution.reorderedPowerOf2(10));   // False
    }
}

Time Complexity

• Computing all the powers of 2 up to ( 2^{30} ) and sorting their digits is ( O(31 \cdot k \log k) ), where ( k ) is the length of the number (since there are 31 potential powers of 2).
• Sorting the digits of n is ( O(m \log m) ), where ( m ) is the number of digits in n.
• Checking membership in a set is average ( O(1) ).

Overall, the time complexity is efficiently handled and is dominated by the ( O(1) ) membership check in the set, making the approach very feasible for typical input sizes.

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?