This post is part of the Algorithms Problem Solving series.
This is the Minimum Operations problem. The description looks like this:
You are given an integer
nums (0-indexed). In one
operation, you can choose an element of the array and increment it
For example, if
nums = [1,2,3], you can choose to increment
nums = [1,**3**,3].
Return the minimum number of operations needed
nums *strictly increasing.*
nums is strictly increasing if
nums[i] < nums[i+1] for
0 <= i < nums.length - 1. An array of
1 is trivially strictly increasing.
Input: nums = [1,1,1] Output: 3 Explanation: You can do the following operations: 1) Increment nums, so nums becomes [1,1,2]. 2) Increment nums, so nums becomes [1,2,2]. 3) Increment nums, so nums becomes [1,2,3].
Input: nums = [1,5,2,4,1] Output: 14
Input: nums =  Output: 0
First solution counting and update the array in place.
def min_operations(nums): previous_num = nums operations = 0 for index, num in enumerate(nums[1:]): if num <= previous_num: new_num = previous_num - num + 1 operations += new_num nums[index + 1] += new_num previous_num = nums[index + 1] return operations
Second and more optimized solution without the need to update the array.
def min_operations(nums): prev, ops = 0, 0 for num in nums: if num <= prev: prev += 1 ops += prev - num else: prev = num return ops
- Learning Python: From Zero to Hero
- Algorithms Problem Solving Series
- Stack Data Structure
- Queue Data Structure
- Linked List
- Tree Data Structure
Have fun, keep learning, and always keep coding!