LeetCode 3669 - Balanced K-Factor Decomposition
We are given two integers, n and k. Our goal is to split n into exactly k positive integers whose product is equal to n. Among all valid decompositions, we want the one where the difference between the largest number and the smallest number is as small as possible.
Difficulty: 🟡 Medium
Topics: Math, Backtracking, Number Theory
Solution
Problem Understanding
We are given two integers, n and k. Our goal is to split n into exactly k positive integers whose product is equal to n.
Among all valid decompositions, we want the one where the difference between the largest number and the smallest number is as small as possible. Since the maximum difference between any two elements in a set is always maxElement - minElement, the objective is equivalent to minimizing:
max(factors) - min(factors)
The output can be returned in any order, but it is often convenient to build the factors in sorted order because the smallest and largest values are then immediately available.
Consider the example n = 44 and k = 3.
Several valid decompositions exist:
1 × 1 × 44 = 44
1 × 2 × 22 = 44
1 × 4 × 11 = 44
2 × 2 × 11 = 44
Their ranges are:
44 - 1 = 43
22 - 1 = 21
11 - 1 = 10
11 - 2 = 9
Therefore, [2,2,11] is optimal.
The constraints are very important:
4 <= n <= 100000
2 <= k <= 5
The value of k is extremely small. This suggests that a carefully designed backtracking solution is practical. Even though there may be many factor combinations, the search depth never exceeds 5 levels.
The problem also guarantees that k is strictly less than the total number of positive divisors of n, which ensures that at least one valid decomposition exists.
Important edge cases include decompositions that require several 1s, prime-heavy numbers where very few factorizations exist, and perfect powers where an exactly balanced decomposition may be possible.
Approaches
Brute Force
A brute-force approach would enumerate every possible sequence of k positive integers whose product equals n.
One way to think about this is to recursively choose the first factor, then the second factor, and so on, until the product constraint is satisfied. Every valid decomposition would be examined, and we would compute its range.
This approach is correct because it explores the entire search space. However, it performs a large amount of redundant work because different permutations of the same factorization are treated as distinct states.
For example:
[2, 2, 11]
[2, 11, 2]
[11, 2, 2]
all represent the same decomposition but would be explored separately.
Key Insight
The key observation is that only the multiset of factors matters, not their order.
Therefore, we can build factors in nondecreasing order. During the recursion, every newly chosen factor must be at least as large as the previous one.
This immediately eliminates duplicate permutations.
Since k ≤ 5 and n ≤ 100000, the number of divisors of any intermediate value is relatively small. We can recursively enumerate divisors of the remaining product and construct all multiplicative partitions in sorted order.
Whenever we obtain exactly k factors whose product equals n, we compute:
largest - smallest
and keep the best decomposition found so far.
Because the search space is already small, this complete enumeration is fast enough.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | Exponential | O(k) | Explores all ordered factorizations, including duplicates |
| Optimal | O(M) | O(k) | Enumerates multiplicative partitions in sorted order, where M is the number of explored factor states |
Here, M is small in practice because k ≤ 5 and n ≤ 100000.
Algorithm Walkthrough
- Maintain a recursive DFS function that receives:
- the remaining product still needing decomposition,
- the number of factors still required,
- the minimum factor allowed next,
- the current factor list.
- Enforce nondecreasing order by requiring every chosen factor to be at least the previous factor. This removes duplicate permutations automatically.
- If only one factor remains to be chosen, the remaining product itself must be the final factor.
- Before accepting that final factor, verify that it is at least the minimum allowed value. Otherwise, the ordering constraint would be violated.
- Construct the completed factorization and compute its range:
lastFactor - firstFactor
Since the factors are stored in sorted order, the first element is the minimum and the last element is the maximum.
6. If this range is smaller than the best range found so far, store the current decomposition as the answer.
7. Otherwise, enumerate all divisors of the current remaining product.
8. For every divisor d that satisfies:
d >= minimumAllowed
choose it as the next factor and recursively decompose:
remaining / d
- Continue until all valid multiplicative partitions have been explored.
Why it works
The recursion generates every valid factorization exactly once because factors are forced to appear in nondecreasing order. Every valid decomposition of n into k factors corresponds to exactly one path in the DFS tree. Since every valid decomposition is examined and we keep the one with the smallest range, the final answer is guaranteed to be optimal.
Python Solution
from typing import List
import math
class Solution:
def minDifference(self, n: int, k: int) -> List[int]:
best_range = float("inf")
best_split: List[int] = []
def dfs(remaining: int, parts_left: int, min_factor: int,
current: List[int]) -> None:
nonlocal best_range, best_split
if parts_left == 1:
if remaining < min_factor:
return
candidate = current + [remaining]
current_range = candidate[-1] - candidate[0]
if current_range < best_range:
best_range = current_range
best_split = candidate[:]
return
divisors = set()
limit = int(math.isqrt(remaining))
for d in range(1, limit + 1):
if remaining % d == 0:
divisors.add(d)
divisors.add(remaining // d)
for d in sorted(divisors):
if d < min_factor:
continue
dfs(
remaining // d,
parts_left - 1,
d,
current + [d]
)
dfs(n, k, 1, [])
return best_split
The implementation follows the recursive strategy directly. The dfs function tracks the remaining product that still needs to be decomposed, the number of factors left to choose, the minimum valid next factor, and the current partial decomposition.
The ordering constraint is enforced through min_factor. Any factor smaller than the previously chosen one is ignored. This guarantees that factors are generated in sorted order and prevents duplicate permutations.
When only one factor remains, the remaining product becomes the final factor. The range is computed and compared against the best answer found so far.
For recursive expansion, all divisors of the current remaining product are generated. Each valid divisor becomes the next factor, and the search continues on the reduced product.
Go Solution
package main
import (
"math"
"sort"
)
func minDifference(n int, k int) []int {
bestRange := int(^uint(0) >> 1)
var bestSplit []int
var dfs func(int, int, int, []int)
dfs = func(remaining int, partsLeft int, minFactor int, current []int) {
if partsLeft == 1 {
if remaining < minFactor {
return
}
candidate := append(append([]int{}, current...), remaining)
currentRange := candidate[len(candidate)-1] - candidate[0]
if currentRange < bestRange {
bestRange = currentRange
bestSplit = append([]int{}, candidate...)
}
return
}
divisorSet := make(map[int]struct{})
limit := int(math.Sqrt(float64(remaining)))
for d := 1; d <= limit; d++ {
if remaining%d == 0 {
divisorSet[d] = struct{}{}
divisorSet[remaining/d] = struct{}{}
}
}
divisors := make([]int, 0, len(divisorSet))
for d := range divisorSet {
divisors = append(divisors, d)
}
sort.Ints(divisors)
for _, d := range divisors {
if d < minFactor {
continue
}
next := append(append([]int{}, current...), d)
dfs(remaining/d, partsLeft-1, d, next)
}
}
dfs(n, k, 1, []int{})
return bestSplit
}
The Go implementation mirrors the Python solution closely. Since Go does not provide Python-style dynamic list copying, slices are explicitly cloned before being passed into recursive calls. Integer overflow is not a concern because the constraints are small and all values remain at most 100000.
Worked Examples
Example 1
n = 100
k = 2
Initial state:
| Variable | Value |
|---|---|
| remaining | 100 |
| partsLeft | 2 |
| current | [] |
Divisors of 100:
1, 2, 4, 5, 10, 20, 25, 50, 100
The DFS explores:
| Chosen First Factor | Final Split | Range |
|---|---|---|
| 1 | [1,100] | 99 |
| 2 | [2,50] | 48 |
| 4 | [4,25] | 21 |
| 5 | [5,20] | 15 |
| 10 | [10,10] | 0 |
| 20 | invalid ordering | - |
| 25 | invalid ordering | - |
| 50 | invalid ordering | - |
| 100 | invalid ordering | - |
Best result:
[10, 10]
Example 2
n = 44
k = 3
Start:
| Variable | Value |
|---|---|
| remaining | 44 |
| partsLeft | 3 |
| current | [] |
Choose first factor 1:
| Current | Remaining |
|---|---|
| [1] | 44 |
Second choices:
| Current | Final Split | Range |
|---|---|---|
| [1,1] | [1,1,44] | 43 |
| [1,2] | [1,2,22] | 21 |
| [1,4] | [1,4,11] | 10 |
Choose first factor 2:
| Current | Remaining |
|---|---|
| [2] | 22 |
Second choice:
| Current | Final Split | Range |
|---|---|---|
| [2,2] | [2,2,11] | 9 |
This is the smallest range encountered.
Final answer:
[2, 2, 11]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(M) | M is the number of explored multiplicative partition states |
| Space | O(k) | Recursion depth and current factor list |
Because k ≤ 5, recursion depth is extremely small. The algorithm explores only valid factorization states, and each recursive level considers divisors of the current remaining product. For n ≤ 100000, this search space is comfortably manageable.
Test Cases
sol = Solution()
# Example 1
assert sorted(sol.minDifference(100, 2)) == [10, 10]
# Example 2
assert sorted(sol.minDifference(44, 3)) == [2, 2, 11]
# Perfect cube
assert sorted(sol.minDifference(64, 3)) == [4, 4, 4]
# Requires a factor of 1
assert sorted(sol.minDifference(13, 2)) == [1, 13]
# Multiple balanced decompositions possible
ans = sorted(sol.minDifference(36, 2))
assert ans == [6, 6]
# Four-factor balanced split
assert sorted(sol.minDifference(81, 4)) == [3, 3, 3, 3]
# Prime-heavy composite
ans = sorted(sol.minDifference(72, 5))
assert len(ans) == 5 and ans[0] * ans[1] * ans[2] * ans[3] * ans[4] == 72
# Boundary-sized value
ans = sol.minDifference(100000, 5)
prod = 1
for x in ans:
prod *= x
assert prod == 100000
# Many ones may appear
assert sorted(sol.minDifference(16, 4)) == [2, 2, 2, 2]
# Another balanced factorization
assert sorted(sol.minDifference(625, 4)) == [5, 5, 5, 5]
Test Summary
| Test | Why |
|---|---|
(100, 2) |
Perfectly balanced two-factor decomposition |
(44, 3) |
Example with multiple competing factorizations |
(64, 3) |
Perfect cube |
(13, 2) |
Prime number requires a factor of 1 |
(36, 2) |
Exact square root split |
(81, 4) |
Perfect power with zero range |
(72, 5) |
Larger factor count |
(100000, 5) |
Upper constraint stress test |
(16, 4) |
Equal repeated factors |
(625, 4) |
Another perfect power decomposition |
Edge Cases
One important edge case occurs when n is prime. In that situation, the only way to decompose the number into multiple positive factors is to use one or more 1s. A naive implementation that only considers factors greater than one would incorrectly conclude that no solution exists. This solution includes 1 as a valid divisor during recursion, so prime numbers are handled naturally.
Another important case is when an exactly balanced decomposition exists. Examples include 64 = 4 × 4 × 4 and 81 = 3 × 3 × 3 × 3. The optimal range is zero. Some greedy approaches may stop early after finding a good decomposition and miss the perfectly balanced one. This implementation exhaustively explores all valid multiplicative partitions and therefore always finds the minimum possible range.
A third edge case involves duplicate factors. For example:
16 = 2 × 2 × 2 × 2
Without an ordering restriction, the recursion would repeatedly generate equivalent permutations of the same decomposition. The nondecreasing-order constraint ensures that every factorization is generated exactly once, eliminating duplicate work and guaranteeing correctness.