Today I have done leetcode's August LeetCoding Challenge with cpp.

August LeetCoding Challenge 30

Description

Minimum Replacements to Sort the Array

You are given a 0-indexed integer array nums. In one operation you can replace any element of the array with any two elements that sum to it.

• For example, consider nums = [5,6,7]. In one operation, we can replace nums[1] with 2 and 4 and convert nums to [5,2,4,7].

Return the minimum number of operations to make an array that is sorted in non-decreasing order.

Example 1:

Input: nums = [3,9,3]
Output: 2
Explanation: Here are the steps to sort the array in non-decreasing order:
- From [3,9,3], replace the 9 with 3 and 6 so the array becomes [3,3,6,3]
- From [3,3,6,3], replace the 6 with 3 and 3 so the array becomes [3,3,3,3,3]
There are 2 steps to sort the array in non-decreasing order. Therefore, we return 2.

Example 2:

Input: nums = [1,2,3,4,5]
Output: 0
Explanation: The array is already in non-decreasing order. Therefore, we return 0. 

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
public:
  long long minimumReplacement(vector<int>& nums) {
    int last = nums.back();
    long long answer = 0;
    for(int i = nums.size() - 2; i >= 0 ;--i) {
      if(nums[i] > last) {
        int parts = nums[i] / last;
        if(nums[i] % last) parts += 1;
        last = nums[i] / parts;
        answer += parts - 1;
      } else {
        last = nums[i];
      }
    }

    return answer;
  }
};

// Accepted
// 47/47 cases passed (49 ms)
// Your runtime beats 99.7 % of cpp submissions
// Your memory usage beats 100 % of cpp submissions (54 MB)