Given an array of N elements where the first element is a non zero positive number M, and the rest N – 1 elements are 0, the task is to calculate the minimum number of steps required to make the entire array equal while abiding by the following rules:
1. The i th element can be increased by one if and only if i-1 th element is strictly greater than the ith element
2. If the i th element is being increased by one then the i+1 th cannot be increased at the same time.(i.e consecutive elements cannot be increased at the same time)
3. Multiple elements can be incremented simultaneously in a single step.
Examples:
Input : N = 3, M = 4
Output : 8
Explanation:
array is 4 0 0
In 4 steps element at index 1 is increased, so the array becomes . In the next 4 steps the element at index 3 is increased so array becomes
Thus, 4 + 4 = 8 operations are required to make all the array elements equal
Input : N = 4, M = 4
Output : 9
Explanation:
The steps are shown in the flowchart given below
Refer to the flowchart given below.
Approach:
To maximise the Number of Increments per Step, more number of Unbalances are created (array[i]>array[i+1]),
Step 1, element 0 >element 1 so element 1 is incremented,
Step 2, element 1> element 2 so element 2 is incremented by 1
Step 3, element 0 > element 1 and element 2> element 3 so element 1 &3 are incremented by 1
Step 4, element 1 > element 2 element 3 > element 4 so element 2 & 4 are incremented
Step 5, element 0> element 1; element 2>element 3 ;element 4> element 5; so element 1, 3, &5 are incremented.
and so on…
Consider the following array,
5 0 0 0 0 0
1) 5 1 0 0 0 0
2) 5 1 1 0 0 0
3) 5 2 1 1 0 0
4) 5 2 2 1 1 0
5) 5 3 2 2 1 1
6) 5 3 3 2 2 1
7) 5 4 3 3 2 2
8) 5 4 4 3 3 2
9) 5 5 4 4 3 3
10) 5 5 5 4 4 3
11) 5 5 5 5 4 4
12) 5 5 5 5 5 4
13) 5 5 5 5 5 5
Notice that after an unbalance is created (i.e array[i]>array[i+1]) the element gets incremented by one in alternate steps. In step 1 element 1 gets incremented to 1, in step 2 element 2 gets incremented to 1, in step 3 element 3 gets incremented to 1, so in step n-1, n-1 th element will become 1. After that n-1 th element is increased by 1 on alternate steps until it reaches the value at element 0. Then the entire array becomes equal.
So the pattern followed by the last element is
(0, 0, 0. 0) till (N – 4) th element becomes 1 which is n-4 steps
and after that,
(0, 0, 1, 1, 2, 2, 3, 3, 4, 4, … M – 1, M – 1, M) which is 2*m + 1 steps.
So the Final Result becomes (N – 3) + 2 * M
There are a few corner cases which need to be handled, viz. When N = 1, array has only a single element, so the number of steps required = 0. and When N = 2, number of steps required equal to M
