FastPrepMinimize the Maximum Array Element

Minimize the Maximum Array Element

Chubb logoChubb● MediumNEW GRADOA
Learn

Problem statement

You are given a nonempty array arr of nonnegative integers. You may perform the following operation zero or more times.

Choose integers l, r, and i such that 0 <= l < r < arr.length, 0 <= i < r, and every derived index is valid: l + r < arr.length and l + i < arr.length. Then assign arr[l + r] = arr[l + i] & arr[r - i], where & is bitwise AND.

Return the minimum possible value of the maximum array element after any finite sequence of legal operations.

Function

minimizeMaximumElement(arr: int[]) → int

Examples

Example 1

arr = [5,12,10,7]return = 5

Index 0 can never be an operation target. A legal sequence can reduce every later value to at most 5, so the optimum is 5.

Example 2

arr = [0,15,9]return = 0

First set index 1 using (l,r,i)=(0,1,0), then set index 2 using (0,2,1).

Constraints

  • 1 <= arr.length <= 200000.
  • 0 <= arr[i] <= 1000000000.
  • You may perform zero operations.

More Chubb problems

See Chubb hiring insights
public int minimizeMaximumElement(int[] arr) {
    // Write your solution here.
}
arr[5,12,10,7]
expected5
Checking account…