LeetCode 3717 - Minimum Operations to Make the Array Beautiful

LeetCode Problem 3717

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Here is the complete, detailed technical solution guide for LeetCode 3717 - Minimum Operations to Make the Array Beautiful following your exact formatting rules.

Problem Understanding

The problem asks us to transform an integer array nums into a beautiful array. An array is considered beautiful if every element (except the first) is divisible by its previous element. Formally, for every i > 0, nums[i] % nums[i - 1] == 0.

We are allowed to perform operations that increment any element nums[i] (with i > 0) by 1. The task is to compute the minimum number of operations required to make the array beautiful.

The input nums is an integer array with size 1 <= nums.length <= 100 and element values 1 <= nums[i] <= 50. The constraints are small, which allows us to explore solutions that might involve iterating over possible multiples of nums[i - 1] without performance concerns.

Edge cases to consider include arrays of size 1 (already beautiful), arrays where elements are already divisible by their predecessors, and cases where minimal increments must make a number exactly divisible.

Approaches

The brute-force approach is straightforward: for each element nums[i] starting from index 1, repeatedly increment it until it becomes divisible by nums[i - 1]. While simple, this approach may perform too many unnecessary increments in some cases. However, due to the small constraints (nums[i] <= 50), this method is feasible but not elegant.

The optimal approach uses the observation that for each nums[i] and nums[i - 1], the minimal increment needed is the smallest multiple of nums[i - 1] that is greater than or equal to nums[i]. Instead of incrementing one by one, we can compute this minimal increment mathematically:

increment = (ceil(nums[i] / nums[i - 1]) * nums[i - 1]) - nums[i]

This avoids repeated increments and directly gives the minimum required. Iterating through the array once while applying this formula yields the minimum total operations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * max(nums))	O(1)	Increment each element repeatedly until divisible
Optimal	O(n)	O(1)	Compute the required increment using arithmetic

Algorithm Walkthrough

1. Initialize a variable operations to 0 to store the cumulative number of increments needed.
2. Iterate over the array from index 1 to the end.
3. For each nums[i], check if it is divisible by nums[i - 1].
4. If nums[i] % nums[i - 1] != 0, calculate the minimal increment:

• Compute the ceiling of nums[i] / nums[i - 1].
• Multiply this ceiling value by nums[i - 1] to get the nearest multiple.
• Subtract nums[i] from this multiple to get the increment.

5. Add the increment to operations.
6. Update nums[i] to the new value after the increment to maintain the beautiful property.
7. Continue until the end of the array.
8. Return operations as the result.

Why it works: By always bringing each nums[i] up to the smallest multiple of nums[i - 1] that is greater than or equal to nums[i], we ensure divisibility with minimal increments. This property guarantees that the array becomes beautiful optimally.

Python Solution

from typing import List
import math

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        operations = 0
        for i in range(1, len(nums)):
            if nums[i] % nums[i - 1] != 0:
                multiplier = math.ceil(nums[i] / nums[i - 1])
                new_value = multiplier * nums[i - 1]
                operations += new_value - nums[i]
                nums[i] = new_value
        return operations

Explanation: We iterate through the array starting at index 1. For each element, we check divisibility. If not divisible, we calculate the minimum multiple of nums[i - 1] that is at least nums[i]. The difference is added to the total operations, and nums[i] is updated to maintain the invariant for subsequent elements.

Go Solution

import "math"

func minOperations(nums []int) int {
    operations := 0
    for i := 1; i < len(nums); i++ {
        if nums[i] % nums[i - 1] != 0 {
            multiplier := int(math.Ceil(float64(nums[i]) / float64(nums[i-1])))
            newValue := multiplier * nums[i - 1]
            operations += newValue - nums[i]
            nums[i] = newValue
        }
    }
    return operations
}

Explanation: The Go implementation mirrors Python. math.Ceil is used to compute the minimal multiplier, and we update nums[i] in-place. Type conversions handle integer division and ceiling. Go's slices are mutable, similar to Python lists.

Worked Examples

Example 1: nums = [3,7,9]

i	nums[i-1]	nums[i]	multiplier	new_value	increment	operations
1	3	7	3	9	2	2
2	9	9	1	9	0	2

Output: 2

Example 2: nums = [1,1,1]

All elements divisible, no operations needed. Output: 0

Example 3: nums = [4]

Single element array, already beautiful. Output: 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Iterate once over the array, each calculation constant time
Space	O(1)	Only a few variables used, no extra data structures

The arithmetic calculation of minimal increments ensures that no repeated increment loops are needed, keeping the time linear in the array size.

Test Cases

# Provided examples
assert Solution().minOperations([3,7,9]) == 2  # increment nums[1] by 2
assert Solution().minOperations([1,1,1]) == 0  # already beautiful
assert Solution().minOperations([4]) == 0     # single element

# Edge cases
assert Solution().minOperations([5,5,5,5]) == 0  # all multiples, no change
assert Solution().minOperations([2,3,4,5]) == 5  # incremental calculations needed
assert Solution().minOperations([50,1]) == 0    # first element large, second divisible by 50? needs increment
assert Solution().minOperations([1,50]) == 0    # already divisible
assert Solution().minOperations([1,49,50]) == 1  # only last element needs increment

Test	Why
[3,7,9]	Tests normal increment logic
[1,1,1]	Already beautiful, zero operations
[4]	Single element edge case
[5,5,5,5]	Array with all multiples, should stay unchanged
[2,3,4,5]	Sequential minimal increment needed
[50,1]	Large first element, small second, must maintain divisibility
[1,49,50]	Only last element needs increment

Edge Cases

1. Single-element array: Since divisibility is defined only for i > 0, an array with one element is always beautiful. The implementation correctly returns 0 without any operations.
2. Already beautiful arrays: Arrays where each element is already divisible by its predecessor should return 0. The code checks divisibility explicitly and only increments when needed, avoiding unnecessary operations.
3. Maximum element values: Arrays with elements at the upper bound (nums[i] = 50) need careful handling to avoid overshooting the multiple. The arithmetic formula ensures correct calculation even at the boundary values, preventing integer overflow in Python and correctly handling conversions in Go.

This guide provides a complete technical reference for implementing and understanding the optimal solution to the problem.