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 of n.

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 ?? [];
    }
    
    

All Problems

All Solutions