Solution

Method 1 – Greedy Backward Splitting

Intuition

To make the array non-decreasing, we process from right to left. For each element, if it's greater than the next, split it into parts so all are ≤ next. The minimum number of splits is ceil(nums[i]/next) - 1.

Approach

Start from the end, set next = nums[-1].
For each nums[i] from n-2 to 0:
- If nums[i] ≤ next, set next = nums[i].
- Else, split nums[i] into parts ≤ next.
- Count splits: parts = ceil(nums[i]/next), ops += parts-1, next = nums[i]//parts.

Code

[{"language":"C++","code":"#include <vector>\n#include <cmath>\nclass Solution {\npublic:\n    long long minimumReplacement(std::vector<int>& nums) {\n        int n = nums.size();\n        long long ops = 0;\n        int next = nums[n-1];\n        for (int i = n-2; i >= 0; --i) {\n            if (nums[i] <= next) next = nums[i];\n            else {\n                int parts = (nums[i]+next-1)/next;\n                ops += parts-1;\n                next = nums[i]/parts;\n            }\n        }\n        return ops;\n    }\n};","lang":"cpp"},{"language":"Go","code":"func minimumReplacement(nums []int) int64 {\n    n := len(nums)\n    ops := int64(0)\n    next := nums[n-1]\n    for i := n-2; i >= 0; i-- {\n        if nums[i] <= next { next = nums[i] } else {\n            parts := (nums[i]+next-1)/next\n            ops += int64(parts-1)\n            next = nums[i]/parts\n        }\n    }\n    return ops\n}","lang":"go"},{"language":"Java","code":"class Solution {\n    public long minimumReplacement(int[] nums) {\n        int n = nums.length, next = nums[n-1];\n        long ops = 0;\n        for (int i = n-2; i >= 0; i--) {\n            if (nums[i] <= next) next = nums[i];\n            else {\n                int parts = (nums[i]+next-1)/next;\n                ops += parts-1;\n                next = nums[i]/parts;\n            }\n        }\n        return ops;\n    }\n}","lang":"java"},{"language":"Kotlin","code":"class Solution {\n    fun minimumReplacement(nums: IntArray): Long {\n        var next = nums.last(); var ops = 0L\n        for (i in nums.size-2 downTo 0) {\n            if (nums[i] <= next) next = nums[i]\n            else {\n                val parts = (nums[i]+next-1)/next\n                ops += parts-1\n                next = nums[i]/parts\n            }\n        }\n        return ops\n    }\n}","lang":"kotlin"},{"language":"Python","code":"class Solution:\n    def minimumReplacement(self, nums: list[int]) -> int:\n        ops, next = 0, nums[-1]\n        for i in range(len(nums)-2, -1, -1):\n            if nums[i] <= next:\n                next = nums[i]\n            else:\n                parts = (nums[i]+next-1)//next\n                ops += parts-1\n                next = nums[i]//parts\n        return ops","lang":"python"},{"language":"Rust","code":"impl Solution {\n    pub fn minimum_replacement(nums: Vec<i32>) -> i64 {\n        let n = nums.len();\n        let mut ops = 0i64;\n        let mut next = nums[n-1];\n        for i in (0..n-1).rev() {\n            if nums[i] <= next { next = nums[i]; }\n            else {\n                let parts = (nums[i]+next-1)/next;\n                ops += (parts-1) as i64;\n                next = nums[i]/parts;\n            }\n        }\n        ops\n    }\n}","lang":"rust"},{"language":"TypeScript","code":"class Solution {\n    minimumReplacement(nums: number[]): number {\n        let ops = 0, next = nums[nums.length-1];\n        for (let i = nums.length-2; i >= 0; i--) {\n            if (nums[i] <= next) next = nums[i];\n            else {\n                const parts = Math.floor((nums[i]+next-1)/next);\n                ops += parts-1;\n                next = Math.floor(nums[i]/parts);\n            }\n        }\n        return ops;\n    }\n}","lang":"typescript"}]

Complexity

⏰ Time complexity: O(n)

Related Tags