3669. Balanced K-Factor Decomposition
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
class Solution {
vector<int> res;
int best;
void dfs(vector<int>& A, vector<int>& now, int n, int k, long long val) {
if(k == 0) {
if(n == val) {
int diff = *max_element(begin(now), end(now)) - *min_element(begin(now), end(now));
if(best > diff) {
best = diff, res = now;
}
}
return;
}
if(val > n) return;
for(auto& a : A) {
now.push_back(a);
dfs(A,now,n,k-1,val * a);
now.pop_back();
}
}
public:
vector<int> minDifference(int n, int k) {
vector<int> divs;
for(long long i = 1; i * i <= n; i++) {
if(n % i) continue;
divs.push_back(i);
if(i * i != n) divs.push_back(n / i);
}
best = INT_MAX;
vector<int> now;
dfs(divs,now,n,k,1);
return res;
}
};
|
