# LeetCode 869: Reordered Power of 2

## Problem Restatement

We are given a positive integer `n`.

We may reorder its digits in any way.

The reordered number:

1. Cannot have leading zeroes.
2. Must use exactly the same digits.

We need to return `True` if some reordering forms a power of two.

Otherwise, return `False`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Positive integer `n` |
| Output | `True` if some digit reordering forms a power of two |
| Constraint | No leading zeroes allowed |

Function shape:

```python
class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        ...
```

## Examples

Example 1:

```python
n = 1
```

The number `1` is already a power of two:

```python
2^0 = 1
```

So the answer is:

```python
True
```

Example 2:

```python
n = 10
```

Possible reorderings:

```python
10
01
```

The second form is invalid because of the leading zero.

`10` is not a power of two.

So the answer is:

```python
False
```

Example 3:

```python
n = 46
```

Reordering the digits gives:

```python
64
```

and:

```python
64 = 2^6
```

So the answer is:

```python
True
```

## First Thought: Try Every Permutation

One direct approach is:

1. Generate every permutation of the digits.
2. Ignore permutations with leading zeroes.
3. Convert each permutation into an integer.
4. Check whether it is a power of two.

This works for small numbers, but the number of permutations grows very quickly.

If there are `d` digits, there can be up to:

```python
d!
```

permutations.

We need something simpler.

## Key Insight

Two numbers can be reordered into each other exactly when they contain the same digits with the same frequencies.

For example:

| Number | Digit counts |
|---|---|
| `128` | one `1`, one `2`, one `8` |
| `821` | one `1`, one `2`, one `8` |

So instead of generating permutations, we compare digit frequency signatures.

The plan:

1. Compute the digit signature of `n`.
2. Generate all powers of two within the valid range.
3. If any power of two has the same digit signature, return `True`.

Since:

```python
n <= 10^9
```

we only need powers:

```python
2^0 through 2^30
```

because:

```python
2^30 = 1073741824
```

and:

```python
2^31 > 10^9
```

## Algorithm

Define a helper function that returns a digit signature.

One simple signature is the sorted digit string.

For example:

| Number | Signature |
|---|---|
| `128` | `"128"` |
| `821` | `"128"` |
| `46` | `"46"` |
| `64` | `"46"` |

Compute:

```python
target = signature(n)
```

Then for every power of two:

1. Compute its signature.
2. Compare with `target`.
3. If equal, return `True`.

If no match exists, return `False`.

## Correctness

Two integers can be reordered into each other exactly when they contain the same digits with the same frequencies.

The signature function captures this property because sorting the digits produces the same result for all reorderings of the same multiset of digits.

Therefore, `n` can be reordered into a power of two if and only if some power of two has the same digit signature as `n`.

The algorithm checks every possible power of two in the valid range, so if such a power exists, the algorithm will find it and return `True`.

If no matching signature exists, then no digit reordering of `n` can form a power of two, so returning `False` is correct.

## Complexity

There are only 31 relevant powers of two.

Let:

```python
d = number of digits in n
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(31 * d log d)` | Sorting digits for each candidate |
| Space | `O(d)` | Temporary strings for signatures |

Since the number of powers is constant, the runtime is effectively constant.

## Implementation

```python
class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        def signature(x: int) -> str:
            return "".join(sorted(str(x)))

        target = signature(n)

        for power in range(31):
            candidate = 1 << power

            if signature(candidate) == target:
                return True

        return False
```

## Code Explanation

The helper function creates a digit signature:

```python
def signature(x: int) -> str:
    return "".join(sorted(str(x)))
```

For example:

| Number | Signature |
|---|---|
| `128` | `"128"` |
| `821` | `"128"` |

Next:

```python
target = signature(n)
```

stores the signature of the input.

Then we generate powers of two:

```python
for power in range(31):
```

The expression:

```python
1 << power
```

computes:

```python
2^power
```

For each candidate power of two:

```python
candidate = 1 << power
```

we compare signatures:

```python
if signature(candidate) == target:
    return True
```

If no match is found after checking all powers:

```python
return False
```

## Testing

```python
def test_reordered_power_of_2():
    s = Solution()

    assert s.reorderedPowerOf2(1) is True
    assert s.reorderedPowerOf2(10) is False
    assert s.reorderedPowerOf2(16) is True
    assert s.reorderedPowerOf2(24) is False
    assert s.reorderedPowerOf2(46) is True
    assert s.reorderedPowerOf2(218) is True
    assert s.reorderedPowerOf2(125) is True

    print("all tests passed")

test_reordered_power_of_2()
```

Test meaning:

| Test | Why |
|---|---|
| `1` | Smallest power of two |
| `10` | Leading-zero reorderings are invalid |
| `16` | Already a power of two |
| `24` | Same digits cannot form a power of two |
| `46` | Reorders to `64` |
| `218` | Reorders to `128` |
| `125` | Reorders to `512` |