Minimize Operations to Balance Shipments
Company: J.P. Morgan
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
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:
```text
quantity = [1, 4, 4]
```
One optimal solution is to increase the last quantity by `1`, producing:
```text
[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:
```text
getMinimumOperations(quantity: int[]) -> long
```
Quick Answer: 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 and the second contains item types j through n - 1, with 1 <= j < n. All units of the same item type must stay in the same consignment.
Before shipping, you may perform operations on the quantities. In one operation, you may increase or decrease the quantity of any one item type by 1, but 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.
Constraints
- 2 <= len(quantity) <= 200000
- 1 <= quantity[i] <= 1000000000
- The answer can be large, so use 64-bit arithmetic in fixed-width languages.
Examples
Input: ([1, 4, 4],)
Expected Output: 1
Explanation: If you split after index 1, the sums are 5 and 4. Increasing the last item by 1 makes the sums 5 and 5, so 1 operation is enough.
Input: ([2, 2],)
Expected Output: 0
Explanation: The only valid split gives sums 2 and 2, which are already equal.
Hints
- For a fixed split point, only the total sum on the left and the total sum on the right matter, not the individual item types.
- One operation changes the difference between the two consignment sums by exactly 1. Use a running prefix sum to evaluate every split in O(n).