Show problems as
Classic problem #3634MediumArrayBinary SearchSliding WindowSorting

Minimum Removals to Balance Array

Real-world version: Discarding Readings Until The Bench Settles
Tracked in this browser only
Read Minimum Removals to Balance Array on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A test bench has produced a batch of readings, listed as readings, and a tolerance factor k.

A batch counts as settled when it still holds at least one reading and its largest reading is no more than k times its smallest reading.

You may throw away any readings you choose. What is left over is judged only on the readings still in it, whatever positions they came from.

Return the smallest number of readings you have to throw away to leave a settled batch.

Examples

Example 1

Input
readings = [10, 1, 9, 8], k = 2
Output
1

Throwing away the reading 1 leaves 10, 9 and 8. The largest of those is 10 and the smallest is 8, and 10 is no more than twice 8, so the batch is settled after one discard.

Example 2

Input
readings = [2, 4], k = 2
Output
0

The batch already holds 4 as its largest and 2 as its smallest, and 4 is exactly twice 2, which the factor allows, so nothing has to go.

Example 3

Input
readings = [1, 2, 3], k = 1
Output
2

With a factor of 1 a settled batch has to have every reading equal, and no reading is repeated here, so only one reading can stay and the other two are thrown away.

Constraints

  • 1 <= readings.length <= 10^5
  • 1 <= readings[i] <= 10^9
  • 1 <= k <= 10^5

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def fewest_discards(readings: list[int], k: int) -> int:
Java
public int fewestDiscards(int[] readings, int k)

More on the same topics