FastPrep
Problem · Dynamic Programming

Make Array Bitonic

● HardOA
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].

Examples
01 · Example 1
arr = [3,3,3,3,3]
return = 6

Answer: 6 (Final Array: [1,2,3,2,1])

02 · Example 2
arr = [1,1,3,1,1]
return = 3

Answer: 3 (Final Array: [0,1,2,1,0])

03 · Example 3
arr = [1,2,1,3,2]
return = 5

Answer: 5 (Final Array: [1,2,1,0,0] or [0,0,1,2,1])

More Amazon problems
drafts saved locally
public int minOperationsToMakeBitonic(int[] arr) {
  // write your code here
}
arr[3,3,3,3,3]
expected6
sign in to submit