3717. Minimum Operations to Make the Array Beautiful 🔒

MediumArrayDynamic Programming

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums.

An array is called beautiful if for every index i > 0, the value of nums[i] is divisible by nums[i - 1]. In other words, each element (starting from the second one) must be a multiple of the element right before it.

You are allowed to perform an operation: pick any element nums[i] where i > 0 and increment it by 1. You can repeat this operation as many times as needed, on any eligible elements.

Note that the first element nums[0] can never be changed.

Your task is to return the minimum total number of increment operations needed to transform the array into a beautiful array.

For example, if nums = [3, 5, 9]:

nums[1] = 5 is not divisible by nums[0] = 3, so we can increment it once to get 6 (1 operation).
Now nums[2] = 9 is not divisible by 6, so we increment it 3 times to get 12 (3 operations).
The array becomes [3, 6, 12], which is beautiful, using a total of 4 operations.

The goal is to find the strategy that minimizes the total number of such operations across the whole array, keeping in mind that the choice made for one element affects what values are valid for the next element.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Dynamic Programming?

This problem maps to Dynamic Programming through a short path in the full flowchart.

The ripple effect of each element's final value on the next element creates overlapping subproblems best solved by DP over reachable values.

Open in Flowchart

Intuition

A natural first thought is to be greedy: for each element, just bump it up to the nearest multiple of the previous element. This seems cheap locally, but it can backfire. A small increase now might leave us with a value whose multiples are far away from the next element, forcing many more operations later. Conversely, paying a bit more now to land on a "nicer" value (one with smaller or better-aligned multiples) can save a lot down the road.

For example, with [2, 3, 4], greedily turning 3 into 4 costs 1 and then 4 is already divisible by 4 — total 2... but turning 3 into 6 costs 3 and then 4 must become 6, costing 2 more. Different choices ripple forward differently, so we cannot decide each element in isolation.

This dependency between consecutive choices is the classic signature of dynamic programming: the optimal cost for the rest of the array depends only on what value the previous element ended up as, not on the entire history of choices.

So the key idea is:

For each position, keep track of every possible final value the current element could take, along with the minimum total cost to reach that state.
When moving to the next element x, for each candidate previous value pre, the next element must become some multiple of pre that is at least x (we can only increment). The cost added is multiple - x.

The last piece of the puzzle is keeping the state space small. Since the values in nums are bounded by a small constant (at most 100 per the constraints), there is never a reason to raise an element beyond 100: any valid multiple of pre that we'd need already exists within that range, and going higher only adds cost. This caps the number of distinct states per position at around 100, making the DP very fast.

In short: greedy fails because choices interact, the interaction only flows through the previous element's final value, and the small value range lets us enumerate all reachable values with their cheapest costs — which is exactly what the hash-map-based DP f in the code does.

Pattern Learn more about Dynamic Programming patterns.

Solution Approach

Solution 1: Dynamic Programming over Reachable Values

We process the array from left to right, maintaining a hash map f that represents all DP states for the element processed so far:

Key: a possible final value of the previous element.
Value: the minimum total number of operations needed to reach a state where the previous element ends up with that value.

Step 1 — Initialization

The first element can never be changed, so there is exactly one starting state:

f = {nums[0]: 0}

This says: the previous element's final value is nums[0], achieved with 0 operations.

Step 2 — Transition

For each subsequent element x, we build a new state map g from the old one f. For every state (pre, s) in f — meaning the previous element ended as pre with total cost s — the current element must become a multiple of pre that is at least x (we can only increment, never decrement).

The smallest such multiple is computed with the ceiling-division trick:

cur = (x + pre - 1) // pre * pre

Here (x + pre - 1) // pre is ⌈x / pre⌉, and multiplying back by pre gives the first multiple of pre not smaller than x.

But the smallest multiple is not always the best choice for the future, so we enumerate all multiples of pre up to the value cap:

while cur <= 100:
    if cur not in g or g[cur] > s + cur - x:
        g[cur] = s + cur - x
    cur += pre

The cost to turn x into cur is exactly cur - x increments, so the new total cost is s + cur - x.
Multiple different pre values can lead to the same cur, so we keep only the minimum cost for each cur — this is the standard DP "take the best way to reach a state" rule.
The bound 100 comes from the problem constraints (nums[i] <= 100): raising an element past 100 only adds cost without enabling any new useful divisibility relationship, so such states can be safely discarded.

After processing element x, we replace f with g and move on:

f = g

Step 3 — Answer

After the last element is processed, every entry in f is a complete valid "beautiful" configuration's cost. The answer is simply the cheapest one:

return min(f.values())

Complexity Analysis

Let n be the length of the array and M = 100 the maximum value.

For each of the n - 1 transitions, there are at most M previous states, and for each state pre we enumerate about M / pre multiples. Summing over all pre gives roughly M · (1 + 1/2 + 1/3 + ... + 1/M) = M · H(M) ≈ M log M work per element.
Time complexity: O(n · M log M).
Space complexity: O(M), since the two hash maps f and g each hold at most M entries.

The pattern used here — "DP where the state is the previous element's final value, stored sparsely in a hash map" — is a common technique whenever element choices chain together and the value domain is small.

Example Walkthrough

Let's trace the algorithm on nums = [6, 13, 24] — a case where the greedy "nearest multiple" choice fails, so it nicely shows why the DP enumerates all reachable values.

Step 0 — Initialization

nums[0] = 6 is fixed, so we start with a single state:

f = {6: 0}

Meaning: the previous element ends as 6, at a total cost of 0 operations.

Step 1 — Process x = 13

There is one state to expand: (pre = 6, s = 0). The current element must become a multiple of 6 that is at least 13. The smallest one is:

cur = (13 + 6 - 1) // 6 * 6 = 18

We then enumerate every multiple of 6 from 18 up to the cap 100, each costing cur - 13 extra operations:

Final value of `nums[1]`	18	24	30	36	...	96
Total cost	5	11	17	23	...	83

So f becomes {18: 5, 24: 11, 30: 17, 36: 23, ..., 96: 83}.

A greedy strategy would commit to 18 here (cheapest locally) and throw the rest away — keep an eye on what that would cost.

Step 2 — Process x = 24

Now we expand every state (pre, s) from f. For each, the smallest multiple of pre that is ≥ 24 is computed, then all further multiples up to 100 are tried:

`pre` (cost `s`)	Multiples of `pre` ≥ 24	New totals `s + cur - 24`
18 (s=5)	36, 54, 72, 90	17, 35, 53, 71
24 (s=11)	24, 48, 72, 96	11, 35, 59, 83
30 (s=17)	30, 60, 90	23, 53, 83
36 (s=23)	36, 72	35, 71
42+ (s ≥ 29)	...	all ≥ 29, dominated

When merging into the new map g, the same cur reachable from different pre values keeps only its minimum cost (e.g., 36 is reachable for 17 via pre = 18 and for 35 via pre = 36 — we keep 17).

Step 3 — Answer

min(f.values()) = 11

The optimal path is 6 → 24 → 24: pay 11 operations to raise 13 all the way to 24, after which nums[2] = 24 needs zero changes. The final array [6, 24, 24] is beautiful since 24 % 6 == 0 and 24 % 24 == 0.

Compare this with greedy: turning 13 into the nearest multiple 18 (5 ops) forces 24 up to 36 (12 ops), for a total of 17 — noticeably worse. This is exactly why the DP keeps every reachable previous value with its cheapest cost: a locally expensive choice (24 instead of 18) turned out to be globally optimal.

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def minOperations(self, nums: List[int]) -> int:
6        # dp maps: {last_value -> min_total_cost}
7        # last_value is the value the previous element was increased to,
8        # and min_total_cost is the minimum number of increment operations
9        # needed so far to reach that state.
10        dp = {nums[0]: 0}
11
12        # Process each subsequent number, building the next DP layer.
13        for num in nums[1:]:
14            next_dp = {}
15            for prev_value, cost in dp.items():
16                # The current number must be raised to a multiple of prev_value.
17                # Round num up to the nearest multiple of prev_value.
18                candidate = (num + prev_value - 1) // prev_value * prev_value
19
20                # Try every valid multiple of prev_value within the value bound (100).
21                while candidate <= 100:
22                    new_cost = cost + candidate - num  # operations to raise num to candidate
23                    # Keep only the cheapest way to end this position at `candidate`.
24                    if candidate not in next_dp or next_dp[candidate] > new_cost:
25                        next_dp[candidate] = new_cost
26                    candidate += prev_value
27
28            # Move on to the next element with the updated states.
29            dp = next_dp
30
31        # The answer is the minimum cost among all possible final values.
32        return min(dp.values())
33

1class Solution {
2    public int minOperations(int[] nums) {
3        // dp maps: (the value that nums[i] was increased to) -> (minimum total operations so far)
4        // We process the array from left to right, keeping all reachable states.
5        Map<Integer, Integer> dp = new HashMap<>();
6
7        // Base case: the first element stays as it is, costing 0 operations.
8        dp.put(nums[0], 0);
9
10        for (int i = 1; i < nums.length; i++) {
11            int current = nums[i];
12            // Next state map for the current position.
13            Map<Integer, Integer> nextDp = new HashMap<>();
14
15            for (Map.Entry<Integer, Integer> entry : dp.entrySet()) {
16                int prevValue = entry.getKey();   // value chosen for nums[i - 1]
17                int prevCost = entry.getValue();  // minimum operations to reach that state
18
19                // The current element must be increased to a multiple of prevValue.
20                // Compute the smallest multiple of prevValue that is >= current.
21                int candidate = (current + prevValue - 1) / prevValue * prevValue;
22
23                // Try every valid multiple up to the upper bound (100).
24                while (candidate <= 100) {
25                    int totalCost = prevCost + (candidate - current);
26
27                    // Keep only the minimum cost for each candidate value.
28                    if (!nextDp.containsKey(candidate) || nextDp.get(candidate) > totalCost) {
29                        nextDp.put(candidate, totalCost);
30                    }
31                    candidate += prevValue;
32                }
33            }
34
35            // Move to the next position.
36            dp = nextDp;
37        }
38
39        // The answer is the minimum cost among all final states.
40        int answer = Integer.MAX_VALUE;
41        for (int cost : dp.values()) {
42            answer = Math.min(answer, cost);
43        }
44        return answer;
45    }
46}
47

1class Solution {
2public:
3    int minOperations(vector<int>& nums) {
4        // dp maps: (final value of the previous element) -> (minimum total
5        // operations needed to fix all elements processed so far)
6        unordered_map<int, int> dp;
7
8        // Base case: the first element stays as it is, costing 0 operations.
9        dp[nums[0]] = 0;
10
11        // Process the remaining elements one by one.
12        for (size_t i = 1; i < nums.size(); ++i) {
13            int cur = nums[i];
14
15            // newDp holds the states after deciding the final value
16            // of the current element.
17            unordered_map<int, int> newDp;
18
19            // Try to extend every previous state.
20            for (const auto& [prevValue, cost] : dp) {
21                // The current element must become a multiple of prevValue
22                // that is >= cur. Round cur up to the nearest multiple.
23                int target = (cur + prevValue - 1) / prevValue * prevValue;
24
25                // Enumerate all valid multiples up to the value cap (100).
26                while (target <= 100) {
27                    // Total cost = previous cost + increments applied
28                    // to raise cur up to target.
29                    int newCost = cost + (target - cur);
30
31                    // Keep only the minimum cost for each target value.
32                    auto it = newDp.find(target);
33                    if (it == newDp.end() || it->second > newCost) {
34                        newDp[target] = newCost;
35                    }
36
37                    target += prevValue;
38                }
39            }
40
41            // Move to the next round of states.
42            dp = move(newDp);
43        }
44
45        // The answer is the minimum cost among all final states.
46        int ans = INT_MAX;
47        for (const auto& [value, cost] : dp) {
48            ans = min(ans, cost);
49        }
50        return ans;
51    }
52};
53

1/**
2 * Calculates the minimum total number of operations needed so that
3 * every element in the array becomes a multiple of the previous element.
4 *
5 * Approach: Dynamic Programming over states.
6 * - State definition: dp maps "the final value of the previous element"
7 *   to "the minimum total cost (sum of increments) to reach that state".
8 * - Transition: for each candidate previous value `prevValue`, the current
9 *   element must be raised to the smallest multiple of `prevValue` that is
10 *   greater than or equal to the current number. We also try all larger
11 *   multiples (bounded by 100) since a bigger current value may allow
12 *   cheaper transitions later.
13 *
14 * @param nums - The input array of positive integers.
15 * @returns The minimum total number of increment operations.
16 */
17function minOperations(nums: number[]): number {
18    // dp: key = value of the previous element after operations,
19    //     value = minimum cost to achieve that configuration.
20    let dp = new Map<number, number>();
21
22    // Base case: the first element stays unchanged with zero cost.
23    dp.set(nums[0], 0);
24
25    // Process each subsequent element and build the next DP layer.
26    for (let i = 1; i < nums.length; i++) {
27        const currentNum = nums[i];
28        const nextDp = new Map<number, number>();
29
30        // Try every possible value of the previous element.
31        for (const [prevValue, cost] of dp.entries()) {
32            // Smallest multiple of prevValue that is >= currentNum.
33            let candidate = Math.floor((currentNum + prevValue - 1) / prevValue) * prevValue;
34
35            // Enumerate all valid multiples up to the upper bound 100.
36            while (candidate <= 100) {
37                // Total cost: previous cost plus increments applied here.
38                const newCost = cost + (candidate - currentNum);
39                const existingCost = nextDp.get(candidate);
40
41                // Keep only the minimum cost for each candidate value.
42                if (existingCost === undefined || existingCost > newCost) {
43                    nextDp.set(candidate, newCost);
44                }
45
46                // Move to the next multiple of prevValue.
47                candidate += prevValue;
48            }
49        }
50
51        // Advance to the next DP layer.
52        dp = nextDp;
53    }
54
55    // The answer is the minimum cost among all final states.
56    return Math.min(...dp.values());
57}
58

Time and Space Complexity

Time Complexity: O(n · M · log M), where n is the length of nums and M is the upper bound of the values (here M = 100).
- The outer loop iterates over all n - 1 elements after the first one, contributing a factor of O(n).
- For each element, the inner loop iterates over every state pre in f. Since every key in f is an integer in the range [1, M], there are at most M distinct states.
- For a fixed state pre, the while loop enumerates multiples of pre that do not exceed M, which takes O(M / pre) iterations.
- Summing over all possible states gives Σ (M / pre) for pre = 1 to M, which is the harmonic series scaled by M, i.e., O(M · log M).
- Combining both parts, the total time is O(n · M · log M). With M = 100 fixed, this can also be viewed as O(n) with a constant factor of roughly M · log M.
Space Complexity: O(M).
- The dictionaries f and g each store at most M key-value pairs, since every key is an integer in [1, M].
- No other data structure grows with the input size, so the extra space is bounded by O(M), which is O(1) when M is treated as a fixed constant (100).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Greedily rounding each element up to the nearest multiple

The most tempting mistake is to skip the DP entirely and just walk left to right, always lifting the current element to the smallest multiple of the previous element:

# WRONG: greedy
def minOperations(self, nums: List[int]) -> int:
    ops = 0
    prev = nums[0]
    for x in nums[1:]:
        cur = (x + prev - 1) // prev * prev  # nearest multiple only
        ops += cur - x
        prev = cur
    return ops

This even matches the walkthrough in the problem statement ([3, 5, 9] → [3, 6, 12]), which makes it look correct. It is not — the choice for one element constrains every element after it, and paying a little more now can save a lot later.

Counterexample: nums = [2, 3, 5, 9]

Greedy path: 3 → 4 (1 op), 5 → 8 (3 ops), 9 → 16 (7 ops) → array [2, 4, 8, 16], total 11 operations.
Optimal path: 3 → 6 (3 ops), 5 → 6 (1 op), 9 → 12 (3 ops) → array [2, 6, 6, 12], total 7 operations.

Spending 2 extra operations to make the second element 6 instead of 4 creates a much friendlier divisor for everything downstream.

Fix: Keep all viable final values per position, not just the cheapest local one. That is exactly what the DP hash map does — for every previous value pre, enumerate every multiple of pre within the bound, and record the minimum cost to reach each candidate value:

while candidate <= 100:
    new_cost = cost + candidate - num
    if candidate not in next_dp or next_dp[candidate] > new_cost:
        next_dp[candidate] = new_cost
    candidate += prev_value

The minimum is then taken only at the very end, after all chained consequences have been priced in.

Pitfall 2: Using floor division instead of ceiling division

Writing the "round up to a multiple" step as:

candidate = num // prev_value * prev_value   # WRONG: rounds DOWN

produces a multiple below num whenever num is not already divisible by prev_value. Since the only allowed operation is increment, a smaller target is unreachable — and worse, cost + candidate - num silently becomes negative, corrupting the DP totals instead of raising an error.

Fix: Use the ceiling-division idiom (or start the loop one multiple higher when needed):

candidate = (num + prev_value - 1) // prev_value * prev_value  # first multiple >= num

Pitfall 3: A value cap that is too strict can empty the DP

The candidate <= 100 bound is justified by "going past the maximum value is never beneficial" — but it can be forced. Consider nums = [99, 100]: the only state is pre = 99, and the smallest multiple of 99 that is >= 100 is 198. The while candidate <= 100 loop never executes, next_dp ends up empty, and min(dp.values()) raises ValueError: min() arg is an empty sequence.

Fix: Always admit the smallest feasible multiple even when it exceeds the cap (among values above the cap, the smallest one dominates all larger ones, so keeping just that one is sufficient):

candidate = (num + prev_value - 1) // prev_value * prev_value
# Record the forced smallest multiple unconditionally...
new_cost = cost + candidate - num
if candidate not in next_dp or next_dp[candidate] > new_cost:
    next_dp[candidate] = new_cost
candidate += prev_value
# ...then enumerate further multiples only within the bound.
while candidate <= 100:
    new_cost = cost + candidate - num
    if candidate not in next_dp or next_dp[candidate] > new_cost:
        next_dp[candidate] = new_cost
    candidate += prev_value

Pitfall 4: Overwriting states instead of taking the minimum

Different previous values can land on the same candidate (e.g., pre = 2 and pre = 3 both reach 6). Writing:

next_dp[candidate] = cost + candidate - num   # WRONG: blind overwrite

keeps whichever transition happened to run last, not the cheapest one, and the error compounds through every later layer.

Fix: Apply the standard DP relaxation rule — only update when the new cost is strictly better:

if candidate not in next_dp or next_dp[candidate] > new_cost:
    next_dp[candidate] = new_cost

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

It's faster

It has better space complexity

Order of computer subproblems does not matter

It has better time complexity

I don't know