Leetcode 869: Reordered Power of 2

Input: A single positive integer `n`.

Example: Input: n = 32

Constraints:

• 1 <= n <= 10^9

Output: Return `true` if it is possible to reorder the digits of `n` to form a power of two, otherwise return `false`.

Example: Output: true

Constraints:

• The output is a boolean value.

Goal: Determine if a permutation of the digits of `n` can result in a power of two.

Steps:

• Count the frequency of each digit in `n`.

• Iterate through all powers of two up to the maximum possible value within the constraints.

• Check if the frequency of digits in any power of two matches the frequency of digits in `n`.

• If a match is found, return `true`; otherwise, return `false`.

Goal: The solution must handle the given range of inputs efficiently.

Steps:

• 1 <= n <= 10^9

• Reordering must not allow leading zeros.

Assumptions:

• The input `n` is always a valid positive integer within the specified range.

• The number can be represented in base 10 without truncation.

• Input: Input: n = 46

• Explanation: The number 46 can be reordered to form 64, which is 2^6. Therefore, the output is `true`.

• Input: Input: n = 123

• Explanation: The number 123 cannot be reordered to form any power of two. Therefore, the output is `false`.

• Input: Input: n = 8

• Explanation: The number 8 is already a power of two (2^3). Therefore, the output is `true`.

Approach: Use a frequency-based approach to compare the digit counts of `n` with the digit counts of all powers of two within the constraints.

Observations:

• A number can only be a power of two if its digits can be reordered to match the digits of an actual power of two.

• There are only 31 powers of two to consider since 2^30 is slightly over 10^9.

• Compare the digit frequencies of `n` with precomputed digit frequencies of all powers of two.

Steps:

• Create a helper function to count the frequency of each digit in a number.

• Precompute the digit frequencies for all powers of two up to 2^30.

• Compute the digit frequencies for the input `n`.

• Iterate through the precomputed powers of two and check if any frequency matches the frequency of `n`.

• If a match is found, return `true`; otherwise, return `false`.

Empty Inputs:

• Not applicable as `n` is always provided.

Large Inputs:

• Inputs near the upper limit of 10^9 should be handled efficiently.

Special Values:

• Inputs like `n = 1` should return `true` since 1 is 2^0.

• Inputs like `n = 0` (if allowed) should return `false` since 0 cannot be a power of two.

Constraints:

• Ensure that leading zeros in permutations are not allowed.

bool reorderedPowerOf2(int n) {
    int c = counter(n);
    for(int i = 0; i < 32; i++)
        if(counter(1<<i) == c) return true;
    return false;
}

int counter(int N) {
    int res = 0;
    for(;N; N/=10) res += pow(10, N%10);
    return res;
}

1 : Function Definition

bool reorderedPowerOf2(int n) {

Defines the `reorderedPowerOf2` function, which checks if the number `n` can be rearranged into a power of 2.

2 : Counter Function Call

    int c = counter(n);

Calls the helper function `counter` to calculate the digit count signature of `n`.

3 : Loop Setup

    for(int i = 0; i < 32; i++)

Starts a loop to check the 32 possible powers of 2 (from 2^0 to 2^31).

4 : Condition Check

        if(counter(1<<i) == c) return true;

Compares the digit count of `n` with the digit count of each power of 2 (calculated as `1 << i`). If they match, returns `true`.

5 : Return False

    return false;

If no power of 2 matches the digit count of `n`, returns `false`.

6 : Helper Function Definition

int counter(int N) {

Defines the helper function `counter`, which calculates the 'digit count signature' of a number `N`.

7 : Variable Initialization

    int res = 0;

Initializes the result variable `res` to store the computed signature of the digits of `N`.

8 : Loop For Digit Counting

    for(;N; N/=10) res += pow(10, N%10);

Uses a loop to process each digit of `N`. For each digit, it adds `10^digit` to the result `res`.

9 : Return Signature

    return res;

Returns the computed digit signature `res`.

Best Case: O(log n)

Average Case: O(log n * k), where k is the number of powers of two to check

Worst Case: O(log n * k)

Description: The complexity is determined by the number of digits in `n` (log n) and the number of powers of two to compare (k).

Best Case: O(1)

Worst Case: O(k)

Description: Space is used for storing the precomputed digit frequencies of powers of two.

Leetcode 869: Reordered Power of 2

Explore →