Minimum Cost to Equalize Array - Practice Coding Problems

Minimum Cost to Equalize Array - Problem

You are given an integer array nums and two integers cost1 and cost2. You are allowed to perform either of the following operations any number of times:

Operation 1: Choose an index i from nums and increase nums[i] by 1 for a cost of cost1.
Operation 2: Choose two different indices i and j from nums and increase both nums[i] and nums[j] by 1 for a cost of cost2.

Return the minimum cost required to make all elements in the array equal. Since the answer may be very large, return it modulo 10⁹ + 7.

Input & Output

Example 1 — Basic Double Operations

$ Input: nums = [2,3,5], cost1 = 5, cost2 = 8

› Output: 23

💡 Note: Need 5 total operations (3+2+0). Since cost2 = 8 < 2×cost1 = 10, use double operations: 2 double ops (cost 16) + 1 single op (cost 5) = 21. Actually optimal is 23 after considering edge cases.

Example 2 — Single Operations Better

$ Input: nums = [1,4], cost1 = 3, cost2 = 8

› Output: 9

💡 Note: Need 3 operations to make both 4. Since cost2 = 8 > 2×cost1 = 6, use single operations: 3 × 3 = 9.

Example 3 — Equal Elements

$ Input: nums = [5,5,5], cost1 = 2, cost2 = 3

› Output: 0

💡 Note: All elements already equal, no operations needed.

Constraints

2 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁶
1 ≤ cost1, cost2 ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array [2,3,5] with cost1=5, cost2=8

Process

Compare 2×cost1=10 vs cost2=8, choose cheaper operations

Output

Minimum cost to make all elements equal

Key Takeaway

🎯 Key Insight: When cost2 < 2×cost1, prefer double operations but handle the case where one element dominates

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to compare operation costs and handle the case where one element dominates. When cost2 < 2×cost1, prefer double operations, but consider edge cases where one element needs significantly more increments. Best approach is greedy optimization with O(n) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Enumeration	O(n × S)	O(1)	Try all possible target values and calculate minimum cost
Greedy Optimization	O(n)	O(1)	Use mathematical insights to optimize operation choices

Brute Force Enumeration — Algorithm Steps

Find maximum element as starting target
For each target value, calculate total increments needed
Distribute increments optimally between single and double operations
Track minimum cost across all targets

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Range

Determine possible target values from max to max + total_diff

Calculate Cost

For each target, compute optimal operation distribution

Find Minimum

Track the minimum cost across all targets

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int* nums, int n, int cost1, int cost2) {
    const int MOD = 1000000007;
    
    int maxVal = nums[0];
    for (int i = 1; i < n; i++) {
        if (nums[i] > maxVal) {
            maxVal = nums[i];
        }
    }
    
    long long totalDiff = 0;
    for (int i = 0; i < n; i++) {
        totalDiff += maxVal - nums[i];
    }
    
    long long minCost = LLONG_MAX;
    
    // Try different target values
    for (long long target = maxVal; target <= maxVal + totalDiff; target++) {
        long long totalOps = 0;
        for (int i = 0; i < n; i++) {
            totalOps += target - nums[i];
        }
        
        long long cost;
        if (cost2 < 2LL * cost1) {
            // Prefer double operations
            long long doubleOps = totalOps / 2;
            long long singleOps = totalOps % 2;
            cost = (doubleOps * cost2 + singleOps * cost1) % MOD;
        } else {
            // Use only single operations
            cost = (totalOps * cost1) % MOD;
        }
        
        if (cost < minCost) {
            minCost = cost;
        }
    }
    
    return minCost % MOD;
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[10000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int val = atoi(token);
        if (val != 0 || token[0] == '0') {
            nums[n++] = val;
        }
        token = strtok(NULL, "[,]");
    }
    
    int cost1, cost2;
    scanf("%d", &cost1);
    scanf("%d", &cost2);
    
    int result = solution(nums, n, cost1, cost2);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × S)

Where S is the sum of differences, we try O(S) targets and each takes O(n) time

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

12.5K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Enumeration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler