Reordered Power of 2 — LeetCode 869 Python Solution
MediumHash TableMathCountingEnumerationSorting
- Problem
- #869
- Pattern
- Sorting
- Reading time
- 3 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- n = 1
- Output
- true
Python solution
Python
class Solution:
def reorderedPowerOf2(self, n: int) -> bool:
def f(x: int) -> List[int]:
cnt = [0] * 10
while x:
x, v = divmod(x, 10)
cnt[v] += 1
return cnt
target = f(n)
i = 1
while i <= 10**9:
if f(i) == target:
return True
i <<= 1
return FalseComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Sorting
Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 869. Reordered Power of 2 is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.
The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 869. Reordered Power of 2?
- LeetCode 869. Reordered Power of 2 is rated Medium on LeetCode.
- What is the time complexity of LeetCode 869. Reordered Power of 2?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 869. Reordered Power of 2?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 869. Reordered Power of 2 cover?
- LeetCode 869. Reordered Power of 2 is tagged Hash Table, Math, Counting, Enumeration and Sorting on LeetCode.