869. Reordered Power of 2

MediumMathCountingEnumerationSorting
Leetcode Link

Problem Description

The problem requires us to determine if it's possible to reorder the digits of a given integer n in such a way that the leading digit is not zero and the result is a power of two. We need to return true if we can achieve this and false otherwise. A power of two is any number in the form of 2^k, where k is a non-negative integer.

Intuition

To solve this problem, we recognize that the order of the digits does not change whether a number is a power of two or not. Only the digits themselves and their counts are important. Therefore, if we can find a power of two that has exactly the same digits as the original number, then we have our solution. Here's how we arrive at the solution approach:

  1. Count the frequency of each digit in the given number n using a function convert(n). This function creates a count array, where each index represents a digit from 0 to 9, and the value at that index represents how many times that digit appears in n.

  2. Generate powers of two and check against the converted count array of n. Starting from 1 (which is 2^0), we generate subsequent powers of two by left-shifting (i <<= 1 which is equivalent to multiplying by 2).

  3. For each power of two, we convert it to the count array form and compare it to the count array of the original number n. If they match, it means we can reorder the digits of n to form this power of two, and we return true.

  4. Continue this process until the power of two exceeds the largest possible integer formed by the digits of n, which is when the power of two surpasses 10^9.

  5. If none of the generated powers of two match the count array of n, we return false, as it is not possible to reorder the digits of n to form a power of two.

This solution ensures that we check all the relevant powers of two up to the size of the original number, without having to generate all permutations of the digits of n, which would be impractical for larger numbers.

Learn more about Math and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Solution Approach

The solution implements a straightforward algorithm that leverages integer operations and simple data structures to determine if the input integer n can be reordered to form a power of two.

The algorithm can be broken down into two main functions:

  1. convert(n): This function takes an integer and converts it into a count array. Here is what the function does in detail:

    • Initialize a count array cnt with 10 elements, all set to 0. Each element cnt[i] corresponds to the frequency of digit i in the input number.
    • Use a while loop to iterate through each digit of n. In each iteration, we perform the operation n, v = divmod(n, 10), which extracts the last digit v of n and reduces n by one decimal place. The divmod function returns a pair of quotient and remainder from division.
    • Increment the count of the extracted digit v in the count array cnt.
    • Return the final count array, which represents the digit frequency of the original integer.

  2. reorderedPowerOf2(n): This function uses the convert(n) function to determine if the number n can be transformed into a power of two.

    • We start with i = 1, which is the smallest power of two (2^0), and a count array s which is the result of convert(n).
    • In a while loop, we keep generating powers of two by left-shifting i (using i <<= 1), and for each i, we convert it to its count array form.
    • Compare the count array of the current power of two to the count array s, if they match (convert(i) == s), it means we can rearrange the digits of n to form this power of two, and we return true.
    • Continue the loop until i exceeds 10^9, at which point we're sure that no power of two of this length exists that could match our original number's digits.
    • If we complete the loop without finding a match, we return false, indicating that n cannot be rearranged into a power of two.

This solution avoids generating permutations, which would be computationally exhausting, especially for larger integers. Instead, it cleverly checks through powers of two by incrementing in a controlled fashion and comparing digit frequencies, thus significantly reducing complexity while providing an accurate answer.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose the input integer n is 46.

First, we need to convert the number 46 into its count array form using the convert(n) function:

  1. Initialize the count array cnt with 10 elements all set to 0.
  2. Extract the digits of 46 iteratively and update their respective counts in cnt.
    • Extract the last digit 6; cnt[6] becomes 1.
    • Update the remaining value of n which is now 4; cnt[4] becomes 1.
  3. The count array cnt for the number 46 is [0, 0, 0, 0, 1, 0, 1, 0, 0, 0].

Now that we have the count array for n, we proceed with the reorderedPowerOf2(n) function:

  1. Start with i = 1, and the count array s representing the number 46, which is [0, 0, 0, 0, 1, 0, 1, 0, 0, 0].
  2. Generate powers of two by left-shifting i and convert each power of two into a count array to compare with s. Here are the first few iterations:
    • For i = 1 (which is 2^0), count array is [1, 0, 0, 0, 0, 0, 0, 0, 0, 0], not a match.
    • For i = 2 (which is 2^1), count array is [0, 0, 1, 0, 0, 0, 0, 0, 0, 0], not a match.
    • For i = 4 (which is 2^2), count array is [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], not a match.
    • Continue incrementing i to find a power of two that matches the count array [0, 0, 0, 0, 1, 0, 1, 0, 0, 0].
  3. When i = 64 (which is 2^6), the count array is [0, 0, 0, 0, 1, 0, 1, 0, 0, 0], which is a match for s.

Since we found a power of two with a count array that matches the count array s of our original number 46, we can confidently return true. This demonstrates that the digits of 46 can be reordered to form the number 64, which is a power of two.

Solution Implementation

1class Solution:
2    def reorderedPowerOf2(self, n: int) -> bool:
3        # Function to convert an integer to a count array of its digits
4        def count_digits(num):
5            count = [0] * 10  # Initialize count array for digits from 0 to 9
6            while num:
7                num, digit = divmod(num, 10)  # Split the number into its last digit and the rest
8                count[digit] += 1  # Increment the corresponding digit count
9            return count
10
11        # Convert the input number to its digits count array
12        input_digit_count = count_digits(n)
13
14        # Start with the smallest power of 2 (2^0 = 1)
15        power_of_two = 1
16      
17        # Loop through powers of 2 within the 32-bit integer range
18        while power_of_two <= 10**9:
19            # Compare the digit count array of the current power of 2 with the input number
20            if count_digits(power_of_two) == input_digit_count:
21                return True  # Found a power of 2 that can be reordered to the input number
22            power_of_two <<= 1  # Go to the next power of 2 by left shifting bits
23      
24        # If no power of 2 matches after going through all 32-bit powers of 2
25        return False
26
1class Solution {
2    // Method to determine if the digits of the input number can be reordered to form a power of two
3    public boolean reorderedPowerOf2(int n) {
4        // Convert the number into a string representation of its digit count
5        String targetDigitCount = convertToDigitCount(n);
6        // Iterate through powers of 2
7        for (int i = 1; i <= 1e9; i <<= 1) { 
8            // Compare the digit count of the current power of 2 with the input number's digit count
9            if (targetDigitCount.equals(convertToDigitCount(i))) {
10                // If both counts match, the digits can be reordered to form a power of two
11                return true;
12            }
13        }
14        // If no power of 2 matches, return false
15        return false;
16    }
17
18    // Helper method to convert a number into a string representing the count of each digit
19    private String convertToDigitCount(int n) {
20        // Array to store the count of digits from 0 to 9
21        char[] digitCount = new char[10]; 
22        // Divide the number into digits and count them
23        while (n > 0) {
24            digitCount[n % 10]++;
25            n /= 10;
26        }
27        // Return a new string constructed from the array of digit counts
28        return new String(digitCount);
29    }
30}
31
1class Solution {
2public:
3    // This function checks if it's possible to reorder digits of 'n' to make it a power of two
4    bool reorderedPowerOf2(int n) {
5        // Convert the original number 'n' to its digits count array
6        vector<int> originalDigitsCount = countDigits(n);
7        // Loop through the powers of 2 within the int range
8        for (int i = 1; i <= 1e9; i <<= 1) {
9            // Compare the digits count of the current power of 2 with the original number
10            if (originalDigitsCount == countDigits(i))
11                return true;
12        }
13        return false;
14    }
15
16    // Helper function to count the digits of a number and return them as a vector
17    vector<int> countDigits(int n) {
18        vector<int> digitCount(10, 0);
19        while (n != 0) {
20            // Increase the count of the rightmost digit
21            digitCount[n % 10]++;
22            // Remove the rightmost digit
23            n /= 10;
24        }
25        return digitCount;
26    }
27};
28
1// This function checks if it's possible to reorder digits of 'n' to make it a power of two
2function reorderedPowerOf2(n: number): boolean {
3    // Convert the original number 'n' to its digit's count array
4    const originalDigitsCount: number[] = countDigits(n);
5    // Loop through the powers of 2 within the range of 32-bit signed integer
6    for (let i = 1; i <= 1e9; i <<= 1) {
7        // Compare the digits count of the current power of 2 with the original number
8        if (arraysEqual(originalDigitsCount, countDigits(i))) {
9            return true;
10        }
11    }
12    return false;
13}
14
15// Helper function to count the digits of a number and return them as an array
16function countDigits(n: number): number[] {
17    const digitCount: number[] = new Array(10).fill(0);
18    while (n !== 0) {
19        // Increase the count of the rightmost digit
20        digitCount[n % 10]++;
21        // Remove the rightmost digit
22        n = Math.floor(n / 10);
23    }
24    return digitCount;
25}
26
27// Helper function to compare if two arrays have the same elements in the same order
28function arraysEqual(a: number[], b: number[]): boolean {
29    if (a.length !== b.length) return false;
30    for (let i = 0; i < a.length; i++) {
31        if (a[i] !== b[i]) return false;
32    }
33    return true;
34}
35
Not Sure What to Study? Take the 2-min Quiz：

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Time and Space Complexity

The time complexity of the code is O(log^2n) where n is the input number. This is because there are logn (base 2) numbers that we compare with the input number's digit count after it's converted. The conversion itself takes O(logn) time since we iterate through each digit in the number (logn digits for a base 10 representation). The space complexity is O(1) because the count array has a fixed size irrespective of the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫