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 <= 1052 <= k <= 5kis 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 ?? []; }