CSES Increasing Array Solution

Problem Statement

Problem Statement Link: CSES 1094: Increasing Array Solution Link

You are given an array of n integers. You want to modify the array so that it is increasing, i.e., every element is at least as large as the previous element.

On each move, you may increase the value of any element by one. What is the minimum number of moves required?

Solution

if __name__=='__main__':
    n = int(input())  # Read the size of the array
    a = list(map(int, input().split()))  # Read the array of integers
    ans = 0  # Initialize the variable to store the answer

    # Iterate through the array starting from the second element
    for i in range(1, n):
        # Check if the current element is smaller than the previous element
        if a[i] < a[i-1]:
            # If yes, calculate the difference and add it to the answer
            ans += a[i-1] - a[i]
            # Update the current element to make the array increasing
            a[i] = a[i-1]

    # Print the final answer, which represents the minimum number of moves
    print(ans)

Explanation

Certainly! Let’s focus specifically on the main logic of the code and explain why it is correct:

1. Objective:
   The main objective is to transform the given array into an increasing sequence using the minimum number of moves, where each move involves incrementing the value of an element by one.
2. Iterative Adjustment:
   The key idea lies in the loop that iterates through the array elements:

   for i in range(1, n):
       if a[i] < a[i-1]:
           ans += a[i-1] - a[i]
           a[i] = a[i-1]

• The loop starts from the second element (i = 1).
• For each iteration, it checks if the current element a[i] is smaller than the previous element a[i-1].

1. Handling Decreasing Pairs:

• If the condition a[i] < a[i-1] is true, it indicates a decreasing pair.
• The code increments ans by the difference between the previous and current elements: ans += a[i-1] - a[i].
• It then updates the current element a[i] to be equal to the previous element a[i-1].

1. Effect of Adjustments:

• By making these adjustments, the code ensures that the array becomes non-decreasing (not strictly increasing) after each iteration of the loop.
• The adjustment guarantees that the current element is at least as large as the previous one.

1. Minimum Moves:

• The ans variable accumulates the total number of moves required to make the entire array non-decreasing.
• The final value of ans represents the minimum number of moves needed to transform the entire array into an increasing sequence.

Correctness:

• The logic correctly identifies and handles decreasing pairs within the array.
• It applies the minimum number of moves necessary to make each element at least as large as its predecessor.
• The final array, after these adjustments, is guaranteed to be strictly increasing.
• The total number of moves (ans) represents the minimum moves required to achieve the strictly increasing array.

In summary, the main logic is correct because it effectively addresses the problem’s requirements, ensuring that the array becomes increasing with the minimum possible moves.

You can find more blogs here.