3669. Balanced K-Factor Decomposition
Medium40.0% acceptance27,213 / 68,019 submissions
Asked by 2 companies
Topics
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.
Hints
Hint 1
First, compute all positive divisors of
n and sort them into a list divs.Hint 2
Use a recursive search
dfs(start, picked, prod, path) that picks the next divisor from divs[start...], multiplies it into prod, and appends to path until you have k factors whose product is n.Hint 3
During the search, keep track of the best
path that minimizes max(path) – min(path) and return it.