mediumBinary SearchPattern: Binary Search on Answer

Min Threshold Value Solution

Problem Statement

Given an array of integers, find the minimum threshold value such that at least 87% of the elements in the array are less than or equal to the threshold.

Examples

Example 1:

Input:[5, 10, 15, 20, 25]

Output:25

Explanation: For 5 residents, at least 87% means we need to satisfy at least ceil(0.87 * 5) = 5 residents. This means all residents must be satisfied. The minimum water amount to satisfy all residents is the maximum requirement, which is 25.

Example 2:

Input:[1, 2, 3, 4, 5]

Output:5

Explanation: For 5 residents, at least 87% means we need to satisfy at least ceil(0.87 * 5) = 5 residents. The minimum water amount to satisfy all residents is the maximum requirement, which is 5.

Example 3:

Input:[5, 15, 25, 35, 45]

Output:45

Explanation: For 5 residents, at least 87% means we need to satisfy at least ceil(0.87 * 5) = 5 residents. The minimum water amount to satisfy all residents is the maximum requirement, which is 45.

Constraints

The input array contains at least 10 elements.
The elements in the array are unique.
The array is sorted in ascending order.
The minimum threshold value is a positive integer.
The maximum possible threshold value is the maximum element in the array.

Time: O(log n) Space: O(1)

Use a binary search algorithm to find the minimum threshold value.

Run, Test & Submit Code

Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.

Solve on Interactive Workspace

Tested Solutions

import math

def min_threshold_value(arr):
  n = len(arr)
  if n == 0:
    return 0
  
  arr.sort()
  
  # Calculate the minimum number of elements that must be less than or equal to the threshold
  min_elements_required = math.ceil(0.87 * n)
  
  # The threshold is the element at the index corresponding to the minimum elements required
  # We need to use min_elements_required - 1 because array indices are 0-based
  return arr[min_elements_required - 1]