Make Array Distinct
Updated
Problem statement
You are given two integer arrays size and cost, each of length n. In one step you can increase any size[i] by 1. That step costs cost[i]. You pay for every increment.
Make all values in size different from each other, and find the minimum total cost to do so.
Function
makeArrayDistinct(size: int[], cost: int[]) → int
Complete the function makeArrayDistinct in the editor.
makeArrayDistinct has the following parameters:
int size[n]: the sizesint cost[n]: the cost of one increment for each size
Returns
int: the minimum total cost to make all values in size distinct
Examples
Example 1
size = [2, 3, 3, 2]cost = [2, 4, 5, 1]return = 7Raising size[i] by 1 costs cost[i]. Go through the sizes from small to large. Size 2 has two items (costs 2 and 1): keep the more expensive one and raise the cost-1 item to 3 (cost 1). Size 3 now has three items (costs 4, 5 and 1): keep the cost-5 item and raise the other two to 4 (cost 4 + 1 = 5). Size 4 has two items (costs 4 and 1): keep the cost-4 item and raise the cost-1 item to 5 (cost 1). Size 5 has one item. The sizes end as [2, 4, 3, 5], all distinct, for a total of 1 + 5 + 1 = 7: the cost-4 item rose by 1 (4) and the cost-1 item rose by 3 (3). The answer is 7.
Example 2
size = [3, 7, 9, 7, 8]cost = [5, 2, 5, 7, 5]return = 6Raising size[i] by 1 costs cost[i]. Only size 7 repeats (costs 2 and 7): keep the cost-7 item and raise the cost-2 item to 8 (cost 2). Size 8 now has two items (costs 5 and 2): raise the cost-2 item to 9 (cost 2). Size 9 again has two items (costs 5 and 2): raise the cost-2 item to 10 (cost 2). Size 10 is free. The sizes end as [3, 10, 9, 7, 8], all distinct, for a total of 2 * (10 - 7) = 6. The answer is 6.
Constraints
1 <= n <= 10^4, wherenis the length ofsizeand ofcost1 <= size[i] <= 10^91 <= cost[i] <= 40
More Amazon interview questions
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Maximal SquareONSITE INTERVIEW · Seen Nov 2026
- Serialize and Deserialize a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Diagonal Traversal of a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Spread Through a GridPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Consistent-Hash Packet RouterPHONE SCREEN · Seen Nov 2026
- Count Connected ComponentsPHONE SCREEN · Seen Nov 2026
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
Similar questions at other companies
- Maximum Easy Tasks After RearrangingIBM · OAIBM interview questions
- Minimum Cost K-Capable ModelsMicrosoft · OAMicrosoft interview questions
- Maximum Distinct Values After Unit AdjustmentsBirla Pivot · OA
- Maximize Revenue from Decreasing InventoryChubb · OAChubb interview questions
- Minimum Distinct Prefix CostGoldman Sachs · OAGoldman Sachs interview questions
- Maximize Minimum Deployment DifficultyJP Morgan Chase · OAJP Morgan Chase interview questions
- Latest Arrival to Catch a BusAutodesk · OAAutodesk interview questions
- EV Charging Cost OptimizationTata Consultancy Services · OATata Consultancy Services interview questions
- Maximize Workday EarningsCitadel · OA · PHONE SCREEN · ONSITE INTERVIEWCitadel interview questions
- Minimum Removals to Balance ArraySalesforce · OASalesforce interview questions