aboutsummaryrefslogtreecommitdiff
path: root/min_replacement_array.py
blob: c0930c1ff47dcca274c53449fc113205e877910a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 2366. Minimum Replacements to Sort the Array
class Solution(object):
    def minimumReplacement(self, nums):
        x = nums[-1]
        ans = 0
        for i in reversed(nums):
            k = (i + x - 1) // x
            x = i // k
            ans += k - 1
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.minimumReplacement([3, 9, 3]))  # expect: 2
    print(obj.minimumReplacement([1, 2, 3, 4, 5]))  # expect: 0