Is Reordered Power of 2 easy or hard?

The problem is rated Medium because the brute-force idea is simple but inefficient. Recognizing that permutations share the same digit frequency and reducing the search to powers of two requires a key insight.

Reordered Power of 2 Python/Java solution

In Python or Java, compute a digit count for n and compare it with counts of numbers generated by shifting powers of two (1 << k). If any count matches, return true. This approach avoids generating permutations and keeps the implementation short and efficient.

How to solve Reordered Power of 2 in O(n)?

Treat the digits as a frequency signature. Count digits of n using an array of size 10. Then generate powers of two within the integer range and compare their digit counts with the signature of n. Since only ~31 powers are checked, the runtime is effectively linear in the number of digits.

What is the best approach for Reordered Power of 2?

The most efficient approach compares digit frequencies. Count how many times each digit appears in n, then compare this signature with every power of two (2^0 to 2^30). If any power of two has the same digit count, the digits can be reordered to form that number. This runs in O(d) time where d is the number of digits.

Is Reordered Power of 2 asked at Google/Amazon/Meta?

Permutation and digit-count problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving frequency counting, anagram detection, or numeric permutations are common screening questions.

What data structure is used in Reordered Power of 2?

The core structure is a fixed-size digit frequency array of length 10. Some implementations use a hash map or a sorted string representation, but the array-based counting approach is the fastest and simplest.

What is the time complexity of Reordered Power of 2?

The optimal digit-count solution runs in O(d) time and O(1) space. You compute the digit frequency of n and compare it against about 31 powers of two. A brute-force permutation approach takes O(d! * d) time because it generates all possible digit arrangements.

Description Solution Video 33:03

869. Reordered Power of 2

Q: How to solve Reordered Power of 2 in O(n)?

Treat the digits as a frequency signature. Count digits of n using an array of size 10. Then generate powers of two within the integer range and compare their digit counts with the signature of n. Since only ~31 powers are checked, the runtime is effectively linear in the number of digits.

Q: What is the best approach for Reordered Power of 2?

The most efficient approach compares digit frequencies. Count how many times each digit appears in n, then compare this signature with every power of two (2^0 to 2^30). If any power of two has the same digit count, the digits can be reordered to form that number. This runs in O(d) time where d is the number of digits.

Q: Is Reordered Power of 2 asked at Google/Amazon/Meta?

Permutation and digit-count problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving frequency counting, anagram detection, or numeric permutations are common screening questions.

Q: What data structure is used in Reordered Power of 2?

The core structure is a fixed-size digit frequency array of length 10. Some implementations use a hash map or a sorted string representation, but the array-based counting approach is the fastest and simplest.

Q: What is the time complexity of Reordered Power of 2?

The optimal digit-count solution runs in O(d) time and O(1) space. You compute the digit frequency of n and compare it against about 31 powers of two. A brute-force permutation approach takes O(d! * d) time because it generates all possible digit arrangements.

Medium66.0% acceptance5 companies

You are given an integer n. We reorder the digits in any order (including the original order) such that the leading digit is not zero.

Return true if and only if we can do this so that the resulting number is a power of two.

Example 1:

Input: n = 1
Output: true

Example 2:

Input: n = 10
Output: false

Constraints:

1 <= n <= 10⁹

Asked at 5 companies

Bloomberg

Google Amazon Microsoft Meta

Topics

33:03

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def reorderedPowerOf2(self, n: int) -> bool:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

Your code is saved on this device.Solution