Minimum Total Cost
Updated
Problem statement
Given an array of integers, the goal is to make all the elements in the array have equal values by applying some number of operations.
The rules of the operations are:
- To apply an operation, one needs to choose a prefix of the array and an integer x (x can be negative).
- In this operation, add x to each element inside this prefix.
- The cost of this operation is |x| (Absolute value of x).
For example, if the array is [1, 4, 2, 1] and the prefix of length 2 and x = -3 are chosen, the array would now become [-2, 1, 2, 1] and the total cost of this operation would be |x| = |-3| = 3.
The total cost is the sum of costs of each operation applied. Find the minimum total cost of making all the elements in the array have equal value.
Note: It is guaranteed that there always exists a series of operations by which all the elements in any array can be equal. These operations can be applied any number of times.
Function
findMinimumCost(arr: List<Integer>) → int
Complete the function findMinimumCost in the editor below.
findMinimumCost has the following parameter:
List<Integer> arr: an array of integers
Examples
Example 1
arr = [1, 2, 1, 5]return = 6The array can be made equal using the following three operations:
- Choose the prefix of length 2 and x = -1. Hence the array now becomes [0, 1, 1, 5]. The cost of this operation is |x| = |-1| = 1.
- Choose the prefix of length 3 and x = 4. Hence the array now becomes [4, 5, 5, 5]. The cost of this operation is |x| = |4| = 4.
- Choose the prefix of length 1 and x = 1. Hence the array now becomes [5, 5, 5, 5]. The cost of this operation is |x| = |1| = 1.
Thus, the total cost = 1 + 4 + 1 = 6, which is the minimum possible.
Constraints
1 <= arr.length <= 1000-2^31 <= arr[i] <= 2^31 - 1The minimum total cost is at most 2^31 - 1.
More JP Morgan Chase interview questions
- Longest Consecutive SequencePHONE SCREEN · Seen Nov 2026
- LFU CacheONSITE INTERVIEW · Seen Nov 2026
- LRU CacheONSITE INTERVIEW · Seen Nov 2026
- Find Total CostOA · Seen Oct 2026
- Minimum Meeting RoomsOA · Seen Oct 2026
- Count Dropped RequestsOA · Seen Oct 2026
- Maximize Binary XOR with a Set-Bit LimitPHONE SCREEN · Seen Oct 2026
- Maximize Minimum Deployment DifficultyOA · Seen Oct 2026
- Task SchedulingOA · Seen Oct 2026
- Substring RemovalOA · Seen Oct 2026
Similar questions at other companies
- Minimum Operations to Sort with Rotations Then SwapsBank of New York Mellon · OA
- Minimum Cost of Left and Right PropagationAmazon · OA
- Minimum Rounds to Complete All TasksInfosys · OAInfosys interview questions
- Reschedule Meetings for Maximum Free TimeFivetran · OAFivetran interview questions
- Maximum Easy Tasks After RearrangingIBM · OAIBM interview questions
- Minimum Cost K-Capable ModelsMicrosoft · OAMicrosoft interview questions
- Maximum ScoreNVIDIA · OANVIDIA interview questions
- Maximum Distinct Values After Unit AdjustmentsBirla Pivot · OA
- Minimize Adjacent Squared-Difference Cost with One InsertionMcKinsey & Company · OAMcKinsey & Company interview questions
- Maximize Revenue from Decreasing InventoryChubb · OAChubb interview questions