FastPrep
Problem · Array

Find Minimum Machines Size

Learn this problem
● MediumAmazonFULLTIMEOA
See Amazon hiring insights

Problem statement

A sequence of n machines is tasked with stocking or retrieving items. You are given the individual stocking/retrieving capacity values of each machine as an integer array, machineCapacity.

The Efficiency of a sequence is defined as the sum of the absolute differences between consecutive machine capacities. For a sequence a of length k, the efficiency is |a[0]-a[1]| + |a[1]-a[2]| + ... + |a[k-2]-a[k-1]|. The efficiency of a sequence consisting of a single machine is 0.

Your task is to remove zero or more machines from the sequence so that the remaining sequence has the same efficiency as the original sequence. When machines are removed, the relative order of the remaining machines must be preserved (the result must be a subsequence of the original array, not a reordering).

Among all subsequences whose efficiency equals the original efficiency, return the minimum possible number of machines (the smallest subsequence length). The remaining sequence must contain at least one machine. If the original array already has all equal elements (efficiency 0), the minimum is 1, since a single machine also has efficiency 0.

If it is impossible to remove any machine while preserving the original efficiency, return n, the original number of machines.

Function

findMinimumMachinesSize(machineCapacity: int[]) → int

findMinimumMachinesSize() has the following parameter(s):

  • int machineCapacity[n]: the stocking/retrieval capacity of each machine

Returns

  • int: the minimum number of machines in the resulting sequence required to achieve the same efficiency score.

Examples

Example 1

machineCapacity = [1, 2, 2, 1, 1]return = 3
Efficiency initially for [1, 2, 2, 1, 1]: |1-2| + |2-2| + |2-1| + |1-1| = 1 + 0 + 1 + 0 = 2. After removing the machines at positions [2] and [3] (0-indexed), the remaining subsequence is [1, 2, 1] (relative order preserved), whose efficiency is |1-2| + |2-1| = 1 + 1 = 2, which equals the original efficiency. No smaller efficiency-preserving subsequence exists, so the minimum number of machines is 3.

Constraints

  • 1 ≤ n ≤ 2×10^5
  • 0 ≤ machineCapacity[i] ≤ 10^9

More Amazon problems

drafts saved locally
public int findMinimumMachinesSize(int[] machineCapacity) {
  // write your code here
}
machineCapacity[1, 2, 2, 1, 1]
expected3
checking account