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
.
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
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
temp.f95:6:31: 6 | integer :: i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z | 1 Error: Symbol βnβ at (1) already has basic type of INTEGER temp.f95:9:4: 9 | nums = [1, 1, 1] | 1 Error: Different shape for array assignment at (1) on dimension 1 (5 and 3) temp.f95:17:4: 17 | nums = [8] | 1 Error: Different shape for array assignment at (1) on dimension 1 (5 and 1)
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
temp.f95:32:12: 32 | nums(j) = nums(j) + 1 | 1 Error: Dummy argument βnumsβ with INTENT(IN) in variable definition context (assignment) at (1) temp.f95:46:5: 46 | use Solution | 1 Fatal Error: Cannot open module file βsolution.modβ for reading at (1): No such file or directory compilation terminated.
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.
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.