Skip to content

3717. Minimum Operations to Make the Array Beautiful πŸ”’

Description

You are given an integer array nums.

An array is called beautiful if for every index i > 0, the value at nums[i] is divisible by nums[i - 1].

In one operation, you may increment any element nums[i] (with i > 0) by 1.

Return the minimum number of operations required to make the array beautiful.

 

Example 1:

Input: nums = [3,7,9]

Output: 2

Explanation:

Applying the operation twice on nums[1] makes the array beautiful: [3,9,9]

Example 2:

Input: nums = [1,1,1]

Output: 0

Explanation:

The given array is already beautiful.

Example 3:

Input: nums = [4]

Output: 0

Explanation:

The array has only one element, so it's already beautiful.

 

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 50​​​

Solutions

Solution 1

Thinking

Later entries may only increase and must become multiples of the previous one. With \(n\le 100\) and \(nums[i]\le 50\), the raised values stay in a small range. DP stores the value written at the previous index and its cost; from each such value we try multiples of it that are at least \(x\) and within a constant cap.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def minOperations(self, nums: List[int]) -> int:
        f = {nums[0]: 0}
        for x in nums[1:]:
            g = {}
            for pre, s in f.items():
                cur = (x + pre - 1) // pre * pre
                while cur <= 100:
                    if cur not in g or g[cur] > s + cur - x:
                        g[cur] = s + cur - x
                    cur += pre
            f = g
        return min(f.values())

 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
class Solution {
    public int minOperations(int[] nums) {
        Map<Integer, Integer> f = new HashMap<>();
        f.put(nums[0], 0);

        for (int i = 1; i < nums.length; i++) {
            int x = nums[i];
            Map<Integer, Integer> g = new HashMap<>();

            for (var entry : f.entrySet()) {
                int pre = entry.getKey();
                int s = entry.getValue();

                int cur = (x + pre - 1) / pre * pre;
                while (cur <= 100) {
                    int val = s + (cur - x);
                    if (!g.containsKey(cur) || g.get(cur) > val) {
                        g.put(cur, val);
                    }
                    cur += pre;
                }
            }
            f = g;
        }

        int ans = Integer.MAX_VALUE;
        for (int v : f.values()) {
            ans = Math.min(ans, v);
        }
        return ans;
    }
}

 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
class Solution {
public:
    int minOperations(vector<int>& nums) {
        unordered_map<int, int> f;
        f[nums[0]] = 0;

        for (int i = 1; i < nums.size(); i++) {
            int x = nums[i];
            unordered_map<int, int> g;
            for (auto [pre, s] : f) {
                int cur = (x + pre - 1) / pre * pre;
                while (cur <= 100) {
                    int val = s + (cur - x);
                    auto jt = g.find(cur);
                    if (jt == g.end() || jt->second > val) {
                        g[cur] = val;
                    }
                    cur += pre;
                }
            }
            f = move(g);
        }

        int ans = INT_MAX;
        for (auto& it : f) {
            ans = min(ans, it.second);
        }
        return ans;
    }
};

 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
func minOperations(nums []int) int {
    f := map[int]int{nums[0]: 0}

    for i := 1; i < len(nums); i++ {
        x := nums[i]
        g := make(map[int]int)
        for pre, s := range f {
            cur := (x + pre - 1) / pre * pre
            for cur <= 100 {
                val := s + (cur - x)
                if old, ok := g[cur]; !ok || old > val {
                    g[cur] = val
                }
                cur += pre
            }
        }
        f = g
    }

    ans := math.MaxInt32
    for _, v := range f {
        ans = min(ans, v)
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function minOperations(nums: number[]): number {
    let f = new Map<number, number>();
    f.set(nums[0], 0);

    for (let i = 1; i < nums.length; i++) {
        const x = nums[i];
        const g = new Map<number, number>();

        for (const [pre, s] of f.entries()) {
            let cur = Math.floor((x + pre - 1) / pre) * pre;
            while (cur <= 100) {
                const val = s + (cur - x);
                const old = g.get(cur);
                if (old === undefined || old > val) {
                    g.set(cur, val);
                }
                cur += pre;
            }
        }
        f = g;
    }

    return Math.min(...f.values());
}

 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
use std::collections::HashMap;

impl Solution {
    pub fn min_operations(nums: Vec<i32>) -> i32 {
        let mut f: HashMap<i32, i32> = HashMap::new();
        f.insert(nums[0], 0);

        for i in 1..nums.len() {
            let x = nums[i];
            let mut g: HashMap<i32, i32> = HashMap::new();

            for (&pre, &s) in f.iter() {
                let mut cur = ((x + pre - 1) / pre) * pre;
                while cur <= 100 {
                    let val = s + (cur - x);
                    match g.get(&cur) {
                        None => {
                            g.insert(cur, val);
                        }
                        Some(&old) => {
                            if val < old {
                                g.insert(cur, val);
                            }
                        }
                    }
                    cur += pre;
                }
            }
            f = g;
        }

        *f.values().min().unwrap()
    }
}

Comments