LeetCode #3669 — MEDIUM

Balanced K-Factor Decomposition

Move from brute-force thinking to an efficient approach using math strategy.

The Problem

Problem Statement

Given two integers n and k, split the number n into exactly k positive integers such that the product of these integers is equal to n.

Return any one split in which the maximum difference between any two numbers is minimized. You may return the result in any order.

Example 1:

Input: n = 100, k = 2

Output: [10,10]

Explanation:

The split [10, 10] yields 10 * 10 = 100 and a max-min difference of 0, which is minimal.

Example 2:

Input: n = 44, k = 3

Output: [2,2,11]

Explanation:

Split [1, 1, 44] yields a difference of 43
Split [1, 2, 22] yields a difference of 21
Split [1, 4, 11] yields a difference of 10
Split [2, 2, 11] yields a difference of 9

Therefore, [2, 2, 11] is the optimal split with the smallest difference 9.

Constraints:

4 <= n <= 10⁵
2 <= k <= 5
k is strictly less than the total number of positive divisors of n.

Step 01

Brute Force Baseline

Problem summary: Given two integers n and k, split the number n into exactly k positive integers such that the product of these integers is equal to n. Return any one split in which the maximum difference between any two numbers is minimized. You may return the result in any order.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Math · Backtracking

Example 1

100
2

Example 2

44
3

Step 02

Core Insight

What unlocks the optimal approach

First, compute all positive divisors of <code>n</code> and sort them into a list <code>divs</code>.
Use a recursive search <code>dfs(start, picked, prod, path)</code> that picks the next divisor from <code>divs[start...]</code>, multiplies it into <code>prod</code>, and appends to <code>path</code> until you have <code>k</code> factors whose product is <code>n</code>.
During the search, keep track of the best <code>path</code> that minimizes max(path) – min(path) and return it.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Upper-end input sizes

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #3669: Balanced K-Factor Decomposition
class Solution {
    static final int MX = 100_001;
    static List<Integer>[] g = new ArrayList[MX];

    static {
        for (int i = 0; i < MX; i++) {
            g[i] = new ArrayList<>();
        }
        for (int i = 1; i < MX; i++) {
            for (int j = i; j < MX; j += i) {
                g[j].add(i);
            }
        }
    }

    private int cur;
    private int[] ans;
    private int[] path;

    public int[] minDifference(int n, int k) {
        cur = Integer.MAX_VALUE;
        ans = null;
        path = new int[k];
        dfs(k - 1, n, Integer.MAX_VALUE, 0);
        return ans;
    }

    private void dfs(int i, int x, int mi, int mx) {
        if (i == 0) {
            int d = Math.max(mx, x) - Math.min(mi, x);
            if (d < cur) {
                cur = d;
                path[i] = x;
                ans = path.clone();
            }
            return;
        }
        for (int y : g[x]) {
            path[i] = y;
            dfs(i - 1, x / y, Math.min(mi, y), Math.max(mx, y));
        }
    }
}

// Accepted solution for LeetCode #3669: Balanced K-Factor Decomposition
const MX = 100001

var g [][]int

func init() {
	g = make([][]int, MX)
	for i := 1; i < MX; i++ {
		for j := i; j < MX; j += i {
			g[j] = append(g[j], i)
		}
	}
}

var (
	cur  int
	ans  []int
	path []int
)

func minDifference(n int, k int) []int {
	cur = math.MaxInt32
	ans = nil
	path = make([]int, k)
	dfs(k-1, n, math.MaxInt32, 0)
	return ans
}

func dfs(i, x, mi, mx int) {
	if i == 0 {
		d := max(mx, x) - min(mi, x)
		if d < cur {
			cur = d
			path[i] = x
			ans = slices.Clone(path)
		}
		return
	}
	for _, y := range g[x] {
		path[i] = y
		dfs(i-1, x/y, min(mi, y), max(mx, y))
	}
}

# Accepted solution for LeetCode #3669: Balanced K-Factor Decomposition
mx = 10**5 + 1
g = [[] for _ in range(mx)]
for i in range(1, mx):
    for j in range(i, mx, i):
        g[j].append(i)


class Solution:
    def minDifference(self, n: int, k: int) -> List[int]:
        def dfs(i: int, x: int, mi: int, mx: int):
            if i == 0:
                nonlocal cur, ans
                d = max(mx, x) - min(mi, x)
                if d < cur:
                    cur = d
                    path[i] = x
                    ans = path[:]
                return
            for y in g[x]:
                path[i] = y
                dfs(i - 1, x // y, min(mi, y), max(mx, y))

        ans = None
        path = [0] * k
        cur = inf
        dfs(k - 1, n, inf, 0)
        return ans

// Accepted solution for LeetCode #3669: Balanced K-Factor Decomposition
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
    pub fn rust_example() {
        // Port the logic from the reference block below.
    }
}

// Reference (java):
// // Accepted solution for LeetCode #3669: Balanced K-Factor Decomposition
// class Solution {
//     static final int MX = 100_001;
//     static List<Integer>[] g = new ArrayList[MX];
// 
//     static {
//         for (int i = 0; i < MX; i++) {
//             g[i] = new ArrayList<>();
//         }
//         for (int i = 1; i < MX; i++) {
//             for (int j = i; j < MX; j += i) {
//                 g[j].add(i);
//             }
//         }
//     }
// 
//     private int cur;
//     private int[] ans;
//     private int[] path;
// 
//     public int[] minDifference(int n, int k) {
//         cur = Integer.MAX_VALUE;
//         ans = null;
//         path = new int[k];
//         dfs(k - 1, n, Integer.MAX_VALUE, 0);
//         return ans;
//     }
// 
//     private void dfs(int i, int x, int mi, int mx) {
//         if (i == 0) {
//             int d = Math.max(mx, x) - Math.min(mi, x);
//             if (d < cur) {
//                 cur = d;
//                 path[i] = x;
//                 ans = path.clone();
//             }
//             return;
//         }
//         for (int y : g[x]) {
//             path[i] = y;
//             dfs(i - 1, x / y, Math.min(mi, y), Math.max(mx, y));
//         }
//     }
// }

// Accepted solution for LeetCode #3669: Balanced K-Factor Decomposition
const MX = 100001;
const g: number[][] = Array.from({ length: MX }, () => []);
for (let i = 1; i < MX; i++) {
    for (let j = i; j < MX; j += i) {
        g[j].push(i);
    }
}

function minDifference(n: number, k: number): number[] {
    let cur = Number.MAX_SAFE_INTEGER;
    let ans: number[] | null = null;
    const path: number[] = Array(k).fill(0);

    function dfs(i: number, x: number, mi: number, mx: number): void {
        if (i === 0) {
            const d = Math.max(mx, x) - Math.min(mi, x);
            if (d < cur) {
                cur = d;
                path[i] = x;
                ans = [...path];
            }
            return;
        }
        for (const y of g[x]) {
            path[i] = y;
            dfs(i - 1, Math.floor(x / y), Math.min(mi, y), Math.max(mx, y));
        }
    }

    dfs(k - 1, n, Number.MAX_SAFE_INTEGER, 0);
    return ans ?? [];
}

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n!)

Space

O(n)

Approach Breakdown

EXHAUSTIVE

O(nⁿ) time

O(n) space

Generate every possible combination without any filtering. At each of n positions we choose from up to n options, giving nⁿ total candidates. Each candidate takes O(n) to validate. No pruning means we waste time on clearly invalid partial solutions.

BACKTRACKING + PRUNING

O(n!) time

O(n) space

Backtracking explores a decision tree, but prunes branches that violate constraints early. Worst case is still factorial or exponential, but pruning dramatically reduces the constant factor in practice. Space is the recursion depth (usually O(n) for n-level decisions).

Shortcut: Backtracking time = size of the pruned search tree. Focus on proving your pruning eliminates most branches.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Overflow in intermediate arithmetic

Wrong move: Temporary multiplications exceed integer bounds.

Usually fails on: Large inputs wrap around unexpectedly.

Fix: Use wider types, modular arithmetic, or rearranged operations.

Missing undo step on backtrack

Wrong move: Mutable state leaks between branches.

Usually fails on: Later branches inherit selections from earlier branches.

Fix: Always revert state changes immediately after recursive call.