Uber OA 2023 - Tower of Swapol
Problem Description:
Lazy Swapnil is playing with the 'Tower of Swapol' game, where there are n towers. Some of these towers contain rings, and the sum of all rings across the towers is exactly n. The goal is to make every tower contain exactly one ring. In a single move, Swapnil can take any number of rings from a tower and move them to either its adjacent left or right tower (but not both simultaneously). Swapnil wants to minimize the number of steps required to make all towers contain only one ring, as he is too lazy to waste extra energy.
You need to find the minimum number of steps required to achieve this goal.
Input Format:
- The first line contains an integer n, the number of towers, and the total number of rings.
- The second line contains an array A of size n, where A[i] represents the number of rings in the i-th tower, it is guaranteed that the sum of all A[i] is exactly n.
Output Format:
- A single integer representing the minimum number of steps required to make all towers contain exactly one ring.
Constraints:
- ( 1 <=n <= 100000 )
- ( 0<=A[i]<=100000 )
- The sum of all A[i]'s is exactly n, meaning the total number of rings across all towers is n.
Sample Testcase:
Input:
4
1 3 0 0
Output:
2
Explanation:
- The array ( A = [1, 3, 0, 0] ) represents the number of rings in each of the four towers.
- The goal is to move rings such that every tower contains exactly one ring.
- In the first step, you could move 2 rings from the second tower to the third tower, making the array ( [1, 1, 2, 0] ).
- In the second step, you move 1 ring from the third tower to the fourth tower, making the array ( [1, 1, 1, 1] ).
- The minimum number of steps required is 2.