Welcome to Subscribe On Youtube
3669. Balanced K-Factor Decomposition
Description
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 <= 105
2 <= k <= 5
k
is strictly less than the total number of positive divisors ofn
.
Solutions
Solution 1
-
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)); } } }
-
class Solution { public: static const int MX = 100001; static vector<vector<int>> g; vector<int> ans; vector<int> path; int cur; vector<int> minDifference(int n, int k) { if (g.empty()) { g.resize(MX); for (int i = 1; i < MX; i++) { for (int j = i; j < MX; j += i) { g[j].push_back(i); } } } cur = INT_MAX; ans.clear(); path.assign(k, 0); dfs(k - 1, n, INT_MAX, 0); return ans; } private: void dfs(int i, int x, int mi, int mx) { if (i == 0) { int d = max(mx, x) - min(mi, x); if (d < cur) { cur = d; path[i] = x; ans = path; } return; } for (int y : g[x]) { path[i] = y; dfs(i - 1, x / y, min(mi, y), max(mx, y)); } } }; vector<vector<int>> Solution::g;
-
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
-
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)) } }
-
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 ?? []; }