# LeetCode 625: Minimum Factorization

## Problem Restatement

We are given a positive integer `num`.

We need to find the smallest positive integer `x` such that the product of the digits of `x` equals `num`.

If no such integer exists, return `0`.

If the answer does not fit in a 32-bit signed integer, return `0`.

The official examples are:

```python
num = 48
```

Output:

```python
68
```

because:

```python
6 * 8 == 48
```

Another example:

```python
num = 15
```

Output:

```python
35
```

because:

```python
3 * 5 == 15
```

Source: LeetCode 625 asks for the smallest positive integer whose digit product equals the input, returning `0` if impossible or outside 32-bit signed integer range.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A positive integer `num` |
| Output | The smallest positive integer whose digits multiply to `num` |
| Impossible case | Return `0` |
| Overflow case | Return `0` if answer exceeds 32-bit signed integer range |

Example function shape:

```python
def smallestFactorization(num: int) -> int:
    ...
```

## Examples

Example 1:

```python
num = 48
```

We can factor `48` as:

```python
6 * 8 = 48
```

So one valid number is:

```python
68
```

The answer is:

```python
68
```

Example 2:

```python
num = 15
```

We can factor `15` as:

```python
3 * 5 = 15
```

The smallest valid number is:

```python
35
```

Example 3:

```python
num = 11
```

There is no digit from `2` to `9` that can help build product `11`.

The digit product cannot contain a prime factor `11`.

So the answer is:

```python
0
```

Example 4:

```python
num = 1
```

The smallest positive integer whose digit product is `1` is:

```python
1
```

So the answer is:

```python
1
```

## First Thought: Try All Numbers

A direct approach is to test numbers one by one.

For each number `x`, compute the product of its digits. If the product equals `num`, return `x`.

This is not practical.

The answer could be large, and checking every integer wastes time. We need to construct the answer from the factorization of `num`.

## Key Insight

Every digit in the answer must be from `2` to `9`, except for the special case `num == 1`.

The digit `1` does not change the product, but it makes the number longer and usually larger. So it is never useful for `num > 1`.

To make the final number as small as possible, we want as few digits as possible first. A number with fewer digits is smaller than any positive number with more digits, unless there are leading zeros, which we do not use here.

So we should use large digit factors whenever possible.

For example:

```python
48 = 2 * 2 * 2 * 2 * 3
```

This could give:

```python
22223
```

But we can combine factors into larger digits:

```python
48 = 6 * 8
```

This gives:

```python
68
```

So we greedily divide by digits from `9` down to `2`.

After collecting the digits, we place them in ascending order to get the smallest number.

## Algorithm

Handle the small case first.

If `num == 1`, return `1`.

Then create an empty list called `digits`.

For each digit `d` from `9` down to `2`:

1. While `num` is divisible by `d`, append `d` to `digits`.
2. Divide `num` by `d`.

After the loop:

1. If `num != 1`, then some factor could not be represented using digits `2` through `9`. Return `0`.
2. Reverse the collected digits so they are in ascending order.
3. Convert them into an integer.
4. If the integer is larger than `2^31 - 1`, return `0`.
5. Otherwise return the integer.

## Correctness

For `num == 1`, the smallest positive integer with digit product `1` is `1`, so returning `1` is correct.

For `num > 1`, digit `1` is never useful because multiplying by `1` does not change the product and only adds another digit to the answer. Therefore every useful digit must be in the range `2` to `9`.

The greedy step tries larger digits first. This minimizes the number of digits because a larger composite digit can replace several smaller factors. For example, using `8` is better than using `2, 2, 2`, because it preserves the same product with fewer digits. Similarly, using `9` is better than using `3, 3`.

After all possible divisions by digits `9` down to `2`, if the remaining `num` is greater than `1`, then it contains a factor that cannot be represented by any digit from `2` to `9`. No valid integer can have that digit product, so returning `0` is correct.

If the remaining `num` is `1`, then the collected digits multiply to the original input. The greedy process used the fewest possible digits because it always replaced factors with the largest valid digit whenever possible.

Among numbers with the same multiset of digits, the smallest integer is obtained by placing digits in ascending order. Since we collected digits from large to small, reversing them gives the smallest possible arrangement.

Therefore the algorithm returns the smallest valid integer when one exists, and returns `0` when no valid integer exists or when the answer exceeds the 32-bit signed integer limit.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(log num)` | Each successful division reduces `num` by at least a factor of `2` |
| Space | `O(log num)` | We store the factor digits |

The loop checks only digits `9` through `2`, so the number of digit choices is constant.

## Implementation

```python
class Solution:
    def smallestFactorization(self, num: int) -> int:
        if num == 1:
            return 1

        digits = []

        for d in range(9, 1, -1):
            while num % d == 0:
                digits.append(d)
                num //= d

        if num != 1:
            return 0

        answer = 0

        for d in reversed(digits):
            answer = answer * 10 + d

            if answer > 2**31 - 1:
                return 0

        return answer
```

## Code Explanation

The special case is handled first:

```python
if num == 1:
    return 1
```

Then we collect digit factors:

```python
digits = []
```

We try digits from `9` down to `2`:

```python
for d in range(9, 1, -1):
```

Whenever `d` divides `num`, we use it as one digit:

```python
while num % d == 0:
    digits.append(d)
    num //= d
```

This extracts as many large digit factors as possible.

After the loop, if `num` is not `1`, factorization failed:

```python
if num != 1:
    return 0
```

Then we build the final number in ascending digit order:

```python
for d in reversed(digits):
    answer = answer * 10 + d
```

The digits were collected from large to small, so reversing gives small to large.

The overflow check is done while building the answer:

```python
if answer > 2**31 - 1:
    return 0
```

If the number fits, we return it:

```python
return answer
```

## Testing

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

    assert s.smallestFactorization(48) == 68
    assert s.smallestFactorization(15) == 35
    assert s.smallestFactorization(1) == 1
    assert s.smallestFactorization(11) == 0
    assert s.smallestFactorization(36) == 49
    assert s.smallestFactorization(100) == 455
    assert s.smallestFactorization(2**31) == 0

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `48` | Basic example with composite factors |
| `15` | Basic example using `3` and `5` |
| `1` | Special case |
| `11` | Impossible prime factor |
| `36` | Chooses `4 * 9`, giving `49` |
| `100` | Builds `455`, since `4 * 5 * 5 = 100` |
| `2^31` | Checks overflow behavior |