Minimum Operations to Make the Array Increasing

🏠 ⬅️ ➑️

You are given an integer array nums (0-indexed). In one operation, you can choose an element of the array and increment it by 1.

  • For example, if nums = [1,2,3], you can choose to increment nums[1] to make nums = [1,**3**,3].

Return the minimum number of operations needed to make nums strictly increasing.

An array nums is strictly increasing if nums[i] < nums[i+1] for all 0 <= i < nums.length - 1. An array of length 1 is trivially strictly increasing.

Example 1:

Input: nums = [1,1,1] Output: 3 Explanation: You can do the following operations: 1) Increment nums[2], so nums becomes [1,1,2]. 2) Increment nums[1], so nums becomes [1,2,2]. 3) Increment nums[2], so nums becomes [1,2,3].

Example 2:

Input: nums = [1,5,2,4,1] Output: 14

Example 3:

Input: nums = [8] Output: 0

Constraints:

  • 1 <= nums.length <= 5000
  • 1 <= nums[i] <= 104

Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct
program main
    implicit none

    integer, parameter :: n = 5
    integer, dimension(n) :: nums
    integer :: i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z

    ! Example 1
    nums = [1, 1, 1]
    write (*, '(A, I0)') 'Example 1: ', minIncrOps(nums)

    ! Example 2
    nums = [1, 5, 2, 4, 1]
    write (*, '(A, I0)') 'Example 2: ', minIncrOps(nums)

    ! Example 3
    nums = [8]
    write (*, '(A, I0)') 'Example 3: ', minIncrOps(nums)

contains

    function minIncrOps(nums) result(res)
        implicit none
        integer, intent(in) :: nums(:)
        integer :: res

        integer :: i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z

        res = 0
        do i = 1, size(nums) - 1
            do j = i + 1, size(nums)
                if (nums(j) >= nums(i)) then
                    cycle
                end if
                res = res + 1
            end do
        end do

    end function minIncrOps

end program main
❌ Compiled
❌ Executed
❌ Correct
module Solution

implicit none

contains

integer function minOperations(nums) result(res)

! Declare variables
integer, intent(in) :: nums(:)
integer :: i, j, count

! Initialize variables
count = 0

! Check if the array is already strictly increasing
if (nums(1) < nums(2)) then
    res = 0
    return
end if

! Loop through the array
do i = 1, size(nums) - 1
    ! Check if the current element is already greater than the next element
    if (nums(i) >= nums(i + 1)) then
        ! Increment the count
        count = count + 1

        ! Loop through the remaining elements
        do j = i + 1, size(nums)
            ! Increment the current element
            nums(j) = nums(j) + 1
        end do
    end if
end do

! Return the minimum number of operations
res = count

end function minOperations

end module Solution

program test

use Solution
implicit none

! Test case 1: [1, 1, 1]
integer, parameter :: nums1(3) = [1, 1, 1]
integer :: res1

! Test case 2: [1, 5, 2, 4, 1]
integer, parameter :: nums2(5) = [1, 5, 2, 4, 1]
integer :: res2

! Test case 3: [8]
integer, parameter :: nums3(1) = [8]
integer :: res3

! Test case 4: [1, 2, 3, 4, 5]
integer, parameter :: nums4(5) = [1, 2, 3, 4, 5]
integer :: res4

! Test case 5: [1, 2, 3, 4, 5, 6]
integer, parameter :: nums5(6) = [1, 2, 3, 4, 5, 6]
integer :: res5

! Test case 6: [1, 2, 3, 4, 5, 6, 7]
integer, parameter :: nums6(7) = [1, 2, 3, 4, 5, 6, 7]
integer :: res6

! Test case 7: [1, 2, 3, 4, 5, 6, 7, 8]
integer, parameter :: nums7(8) = [1, 2, 3, 4, 5, 6, 7, 8]
integer :: res7

! Test case 8: [1, 2, 3, 4, 5, 6, 7, 8, 9]
integer, parameter :: nums8(9) = [1, 2, 3, 4, 5, 6, 7, 8, 9]
integer :: res8

! Test case 9: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
integer, parameter :: nums9(10) = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
integer :: res9

! Test case 10: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
integer, parameter :: nums10(11) = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
integer :: res10

! Test case 11: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
integer, parameter :: nums11(12) = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
integer :: res1
🌐 Data from online sources
def min_operations(nums):
    operations = 0
    for i in range(1, len(nums)):
        if nums[i] <= nums[i - 1]:
            operations += (nums[i - 1] - nums[i]) + 1
            nums[i] = nums[i - 1] + 1
    return operations

The algorithm iterates through the input array nums from the second element (index 1) to the end. For each element, if it is less than or equal to its previous element, we need to increment it to make the array strictly increasing. We calculate the difference between the current element and the previous element and add 1 to it to find the required number of increments. We then update both the element in the array and the total count of operations. At the end, we return the total count of operations.

🌐 Data from online sources
int min_operations(vector<int>& nums) {
    int operations = 0;
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] <= nums[i - 1]) {
            operations += (nums[i - 1] - nums[i]) + 1;
            nums[i] = nums[i - 1] + 1;
        }
    }
    return operations;
}

The algorithm iterates through the input array nums from the second element (index 1) to the end. For each element, if it is less than or equal to its previous element, we need to increment it to make the array strictly increasing. We calculate the difference between the current element and the previous element and add 1 to it to find the required number of increments. We then update both the element in the array and the total count of operations. At the end, we return the total count of operations.