Problem Brief
Make Array Bitonic
OA
See Amazon online assessment and hiring insights
Given an array arr of n integers, in a single operation, one can reduce any element of the array by 1. Find the minimum number of operations required to make the array a bitonic* array.
- A bitonic array can have any number of zeros in prefix and suffix. The non-zero part should increase from 1 to some integer k and then decrease to 1.
Example of a bitonic array: [0,1,2,3,2,1,0,0].
1Example 1
Input
arr = [3,3,3,3,3]
Output
6
Explanation
Answer: 6 (Final Array: [1,2,3,2,1])
2Example 2
Input
arr = [1,1,3,1,1]
Output
3
Explanation
Answer: 3 (Final Array: [0,1,2,1,0])
3Example 3
Input
arr = [1,2,1,3,2]
Output
5
Explanation
Answer: 5 (Final Array: [1,2,1,0,0] or [0,0,1,2,1])