Abstract / Summary

Check if digits of a number can be rearranged to form a power of two.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 66% (300k+ submissions).

Typical patterns to solve this problem:

• Counting
• Enumeration
• Hash Table
• Math
• Sorting

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation determines whether the digits of a given integer can be rearranged to form a power of two. It does this by generating powers of two whose decimal length matches that of the input and comparing the multiset of digits using sorted strings. The algorithm stops as soon as a matching power is found or when the length of the generated power exceeds the length of the input.

Key Steps

Convert the input to a string

The first operation creates a string representation of the input number, which is later used for length comparison and digit sorting.

nn = str(n)

Find the smallest power of two with at least the same length

A left-shift (<<= 1) is used to double the value of two until its string length is no longer shorter than the length of nn. This ensures that the subsequent loop starts with the smallest candidate that could possibly match the digit count.

two = 1
while len(str(two)) < len(nn):
    two <<= 1

Iterate over powers of two of equal length

The core loop runs while the current power of two has the same number of digits as the input. Inside the loop the digits of the current power and the input are sorted and compared. If they match, the function returns True. Otherwise the power is doubled again with another left-shift.

while len(str(two)) == len(nn):
    if sorted(str(two)) == sorted(nn):
        return True
    two <<= 1

Return False when no match is found

If the loop exits because the length of two has grown beyond the length of nn, the function concludes that no permutation can form a power of two and returns False.

return False

Edge Cases Handled

When the input consists of a single digit, the initial while-loop that expands two does not execute because the length condition is already satisfied. The subsequent loop then checks the only one-digit powers of two (1, 2, 4, 8).

If the input is 1, the sorted digit comparison succeeds on the first iteration, causing an immediate True return.

For inputs that are already powers of two, the algorithm still works because the sorted digit strings are identical, leading to a match without any extra work.

When the input contains repeated digits, such as 112, the sorting step captures the exact multiset of digits, allowing the algorithm to correctly identify that 112 can be reordered to 121 (which is not a power of two) and consequently return False.

The method also gracefully handles the maximum integer size supported by Python because the loop terminates as soon as the length of the generated power exceeds the length of the input, preventing unbounded growth.

Performance Optimizations

The use of the left-shift operator (<<=) to double the candidate power of two is a low-overhead arithmetic operation compared to multiplication, which reduces the per-iteration cost.

Sorting the string representations of the numbers provides a concise way to compare digit multisets without constructing explicit frequency tables. Since the length of the strings is bounded by the number of digits in the input, the sorting work remains limited.

The algorithm limits the search space to powers of two that share the same digit count as the input. By breaking out of the loop as soon as the length diverges, it avoids unnecessary generation and comparison of larger powers, which would never match the digit count.

Early termination on a successful match (return True) prevents further unnecessary iterations, ensuring that the best-case scenario runs in constant time relative to the number of candidate powers examined.

Overall, the combination of bitwise doubling, length-based loop control, and sorted-string comparison yields an implementation that is both concise and efficient for the problem domain.

Imagine you have a big bucket filled with wooden blocks that have numbers written on them. You want to see if you can rearrange the blocks to make a special kind of number that is always made by doubling a number over and over again starting from one.

The code first looks at the number of digits in your number so it knows how big the target numbers should be. It ignores any numbers that have too few or too many digits because they definitely cannot be a match. Once it finds a candidate that has the exact same length as your number, it lines up the blocks from both numbers in order from smallest to largest. If the line of blocks from your number looks exactly like the line of blocks from the special power of two, then the answer is a big yes. If the blocks do not match, the computer doubles the number to get a new candidate and tries again until it either finds a match or runs out of numbers that are the right size.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: logarithmic
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python	Java						TS
	WalkCCC	C++	Python	Java
	leetcode.ca	C++	Python	Java		Rust		Go		TS
	LeetcodeHelp	C++	Python	Java
	Progiez	C++	Python	Java
github	black-shadows	C++
	charles-wangkai			Java
	everthis				JS
	fartem						Ruby
	fsq	C++
	halfrost							Go
	JoshCrozier				JS
	keineahnung2345	C++
	lkwq007		Python
	ruoru					Rust
	suxrobGM								C#
	trung-hn		Python
	varunu28			Java
	vthwang			Java
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality