3717. Minimum Operations to Make the Array Beautiful
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.
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
|
long long dp[101][101];
class Solution {
long long helper(vector<int>& A, int at, int target) {
if(A[at] > target) return INT_MAX;
if(at == 0) return target != A[0] ? INT_MAX : 0;
if(dp[at][target] != -1) return dp[at][target];
long long& res = dp[at][target] = INT_MAX, diff = target - A[at], sq = sqrt(target);
for(int i = 1; i <= sq; i++) {
if(target % i) continue;
res = min(res, diff + min(helper(A,at-1,i), helper(A,at-1,target / i)));
}
return res;
}
public:
int minOperations(vector<int>& nums) {
memset(dp,-1,sizeof dp);
long long res = LLONG_MAX;
for(int i = nums.back(); i <= 100; i++) {
res = min(res, helper(nums, nums.size() - 1, i));
}
return res;
}
};
|
