Make K-Subarray Sums Equal - Practice Coding Problems

Make K-Subarray Sums Equal - Problem

Array Math Greedy Sorting Number Theory Medium

You are given a 0-indexed integer array arr and an integer k. The array arr is circular. In other words, the first element of the array is the next element of the last element, and the last element of the array is the previous element of the first element.

You can do the following operation any number of times:

Pick any element from arr and increase or decrease it by 1.

Return the minimum number of operations such that the sum of each subarray of length k is equal.

A subarray is a contiguous part of the array.

Input & Output

Example 1 — Basic Circular Array

$ Input: arr = [2,5,3,9,5,3], k = 3

› Output: 5

💡 Note: Need to make all 3-subarrays equal: [2,5,3], [5,3,9], [3,9,5], [9,5,3], [5,3,2], [3,2,5]. Optimal solution groups elements by GCD pattern and uses medians.

Example 2 — Small Array

$ Input: arr = [1,4,1,3], k = 2

› Output: 1

💡 Note: 4-subarrays of length 2: [1,4], [4,1], [1,3], [3,1]. Elements at even positions (1,1) and odd positions (4,3) form groups. Operations: |1-1| + |4-3.5| + |1-1| + |3-3.5| = 1

Example 3 — No Operations Needed

$ Input: arr = [2,2,2,2], k = 2

› Output: 0

💡 Note: All elements are already equal, so all k-subarrays have equal sums. No operations needed.

Constraints

1 ≤ arr.length ≤ 10⁵
1 ≤ arr[i] ≤ 10⁹
1 ≤ k ≤ arr.length

Visualization

Tap to expand

Understanding the Visualization

Input

Circular array [2,5,3,9,5,3] with k=3 subarrays

Process

Group elements by GCD pattern and find optimal values

Output

Minimum 5 operations to equalize all k-subarray sums

Key Takeaway

🎯 Key Insight: Elements at positions with same remainder mod gcd(n,k) must be equal

Asked in

G Google 15 f Meta 12 M Microsoft 8

The key insight is that elements at positions with the same remainder when divided by gcd(n,k) must have equal values for all k-subarrays to be equal. Best approach uses mathematical grouping with medians for optimal operations. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Approach - GCD Groups	O(n log n)	O(n)	Group elements by GCD pattern and find optimal values using medians
Brute Force - Try All Target Sums	O(n³)	O(n)	Try every possible target sum and calculate minimum operations

Mathematical Approach - GCD Groups — Algorithm Steps

Step 1: Calculate g = gcd(n, k) to find independent groups
Step 2: Group elements by their position modulo g
Step 3: For each group, find the median value
Step 4: Sum operations needed to change all elements to their group's median

Visualization

Tap to expand

Step-by-Step Walkthrough

Find GCD Groups

Group elements by position mod gcd(n,k)

Find Medians

Sort each group and find median value

Calculate Operations

Sum operations to change all elements to group medians

Code -

solution.c — C

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

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

long long solution(int* arr, int arrSize, int k) {
    if (k == 1) return 0;
    
    int g = gcd(arrSize, k);
    int** groups = (int**)malloc(g * sizeof(int*));
    int* groupSizes = (int*)calloc(g, sizeof(int));
    
    // Count group sizes
    for (int i = 0; i < arrSize; i++) {
        groupSizes[i % g]++;
    }
    
    // Allocate groups
    for (int i = 0; i < g; i++) {
        groups[i] = (int*)malloc(groupSizes[i] * sizeof(int));
        groupSizes[i] = 0; // Reset for filling
    }
    
    // Fill groups
    for (int i = 0; i < arrSize; i++) {
        int groupIdx = i % g;
        groups[groupIdx][groupSizes[groupIdx]++] = arr[i];
    }
    
    long long totalOps = 0;
    
    // For each group, find median and calculate operations
    for (int i = 0; i < g; i++) {
        if (groupSizes[i] <= 1) continue;
        
        qsort(groups[i], groupSizes[i], sizeof(int), compare);
        int median = groups[i][groupSizes[i] / 2];
        
        // Calculate operations to make all elements equal to median
        for (int j = 0; j < groupSizes[i]; j++) {
            totalOps += abs(groups[i][j] - median);
        }
    }
    
    // Free memory
    for (int i = 0; i < g; i++) {
        free(groups[i]);
    }
    free(groups);
    free(groupSizes);
    
    return totalOps;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int arr[1000];
    int arrSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            arr[arrSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%lld\n", solution(arr, arrSize, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Grouping elements takes O(n), sorting each group for median takes O(n log n)

⚡ Linearithmic

Space Complexity

O(n)

Storage for groups and temporary arrays for median calculation

⚡ Linearithmic Space

29.4K Views

Medium Frequency

~25 min Avg. Time

890 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

Mathematical Approach - GCD Groups — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler