Question

SnowFlake | OA | SDE-Internship | Coding Questions and Solutions | 2023 |

Answer 1

Given an array arr of n positive integers, the following operation can be performed any number of times. Use a 1-based index for the array.

 

• Choose any i such that 2<=i<=n
• Choose any x such that 1<=i<=arr[i]
• Set arr[i-1] to arr[i-1]+x
• Set arr[i] to arr[i]-x

 

Minimize the maximum value of arr using the above operation and return value.

 

Example: arr=[1,5,7,6]
arr becomes [1,9,3,6] after choosing i=3 and x=4 as x<=arr[3], i.e. 4<7
arr becomes [5,5,3,6] after choosing i=2 and x=4 as x<=arr[2]
arr becomes [5,5,4,5] after choosing i=4 and x=1 as x<=arr[4]
output = 5

 

Example : arr = [5,15,19]
output = 13

 

Example : arr = [10,3,5,7]
output = 10