869. Reordered Power of 2
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:
-
Count the frequency of each digit in the given number
n
using a functionconvert(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 inn
. -
Generate powers of two and check against the converted count array of
n
. Starting from1
(which is2^0
), we generate subsequent powers of two by left-shifting (i <<= 1
which is equivalent to multiplying by 2). -
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 ofn
to form this power of two, and we returntrue
. -
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 surpasses10^9
. -
If none of the generated powers of two match the count array of
n
, we returnfalse
, as it is not possible to reorder the digits ofn
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.
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:
-
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 to0
. Each elementcnt[i]
corresponds to the frequency of digiti
in the input number. - Use a while loop to iterate through each digit of
n
. In each iteration, we perform the operationn, v = divmod(n, 10)
, which extracts the last digitv
ofn
and reducesn
by one decimal place. Thedivmod
function returns a pair of quotient and remainder from division. - Increment the count of the extracted digit
v
in the count arraycnt
. - Return the final count array, which represents the digit frequency of the original integer.
- Initialize a count array
-
reorderedPowerOf2(n)
: This function uses theconvert(n)
function to determine if the numbern
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 arrays
which is the result ofconvert(n)
. - In a while loop, we keep generating powers of two by left-shifting
i
(usingi <<= 1
), and for eachi
, 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 ofn
to form this power of two, and we returntrue
. - Continue the loop until
i
exceeds10^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 thatn
cannot be rearranged into a power of two.
- We start with
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
- Initialize the count array
cnt
with 10 elements all set to0
. - Extract the digits of
46
iteratively and update their respective counts incnt
.- Extract the last digit
6
;cnt[6]
becomes1
. - Update the remaining value of
n
which is now4
;cnt[4]
becomes1
.
- Extract the last digit
- The count array
cnt
for the number46
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:
- Start with
i = 1
, and the count arrays
representing the number46
, which is[0, 0, 0, 0, 1, 0, 1, 0, 0, 0]
. - Generate powers of two by left-shifting
i
and convert each power of two into a count array to compare withs
. Here are the first few iterations:- For
i = 1
(which is2^0
), count array is[1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
, not a match. - For
i = 2
(which is2^1
), count array is[0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
, not a match. - For
i = 4
(which is2^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]
.
- For
- When
i = 64
(which is2^6
), the count array is[0, 0, 0, 0, 1, 0, 1, 0, 0, 0]
, which is a match fors
.
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
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.
Which data structure is used to implement priority queue?
Recommended Readings
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 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 Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.