FastPrep
Problem · Dynamic Programming

Make Array Bitonic

Learn this problem
● HardAmazonOA
See Amazon hiring insights

Problem statement

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

Function

minOperationsToMakeBitonic(arr: int[]) → int

Examples

Example 1

arr = [3,3,3,3,3]return = 6

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

Example 2

arr = [1,1,3,1,1]return = 3

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

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
checking account