Katkat
Back

Minimize Operations to Balance Shipments

J.P. MorganSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This question evaluates algorithmic optimization and array partitioning skills, focusing on modeling minimal integer adjustments to equalize partition sums and demonstrating numerical reasoning under constraints.

A shop has n item types, where quantity[i] is the positive integer quantity of the i-th item type. The item types must be shipped in two non-empty consignments by choosing a split point j such that:

  • The first consignment contains item types 0 through j - 1.
  • The second consignment contains item types j through n - 1.
  • 1 <= j < n.
  • All units of the same item type must stay in the same consignment.

You may perform operations before the final shipment. In one operation, you may increase or decrease the quantity of any one item type by 1. Every final quantity must remain positive.

Choose the split point and the quantity adjustments optimally so that the total quantity in the first consignment equals the total quantity in the second consignment.

Return the minimum number of operations required.

Example:

quantity = [1, 4, 4]

One optimal solution is to increase the last quantity by 1, producing:

[1, 4, 5]

Then choose j = 2, so the two consignments are [1, 4] and [5], both with total quantity 5.

The minimum number of operations is 1.

Implement:

getMinimumOperations(quantity: int[]) -> long