IARRAY - Editorial

Problem Link:
Practice
Contest

Author: murugappan_s
Testers: sdssudhu,msv99999
Editorialist: murugappan_s

DIFFICULTY: Easy-Medium

PREREQUISITES: Greedy Algorithms

PROBLEM:
We have two arrays(A and B) each of size N. In one step we can choose any two index l and r such that 1≤l≤r≤N and increment B[i] by 1 for l≤i≤r.

Find the minimum number of steps required to make both are identical.

CONSTRAINTS:

  • 1≤N≤100000
  • 0≤B[i]≤A[i]≤10^9

SOLUTION:

There are different approaches to solve this problem. We would be discussing the greedy strategy here, but there is a nice divide-and-conquer solution, which is left for the audience to think.

Lets compute the difference array(C) where C[i]=A[i]-B[i].

Lets assume that we have somehow made the array identical for the first i-1 elements. Now,there are two cases to consider

Let number of steps performed till now be STEPS

Case 1: C[i]<=C[i-1]
In this case, the number of times the ith element has to be incremented is <= the number of times the (i-1)th element has to be incremented. So we can greedily choose ith element when (i-1)th element is chosen, thereby spending no extra effort for the ith element. Which implies that there is no change in the value of STEPS.

Case 2: C[i]>C[i-1]
In this case, the number of times the ith element has to be incremented is > the number of times the (i-1)th element has to be incremented. To minimize the extra effort required for the ith element, first we try to choose ith element whenever (i-1)th element is chosen. So, the ith element would have increased by C[i-1], now what is left is C[i]-C[i-1]. For the difference alone we have to take ith element separately without the help of (i-1)th element. Which implies that STEPS increases by C[i]-C[i-1].

Time Complexity: O(N)

1 Like