Minimum Operations to Make Array Sum Divisible by K

Minimum Operations to Make Array Sum Divisible by K - Problem

Array Math Easy

You are given an integer array nums and an integer k.

You can perform the following operation any number of times:

Select an index i and replace nums[i] with nums[i] - 1

Return the minimum number of operations required to make the sum of the array divisible by k.

Input & Output

Example 1 — Basic Case

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

› Output: 4

💡 Note: Sum = 3+1+4+2 = 10. Since 10 % 6 = 4, we need 4 operations to reduce the sum by 4 and make it divisible by 6.

Example 2 — Already Divisible

$ Input: nums = [2,4], k = 3

› Output: 0

💡 Note: Sum = 2+4 = 6. Since 6 % 3 = 0, the sum is already divisible by 3, so 0 operations needed.

Example 3 — Single Element

$ Input: nums = [5], k = 3

› Output: 2

💡 Note: Sum = 5. Since 5 % 3 = 2, we need 2 operations to reduce 5 to 3, making it divisible by 3.

Constraints

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

Visualization

Tap to expand

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Meta 12

The key insight is using modular arithmetic. Calculate the sum of all elements and find remainder when divided by k. The remainder tells us exactly how many operations are needed. Best approach is the mathematical solution with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(k^n)	O(1)	Try all possible ways to reduce array elements until sum is divisible by k
Mathematical Solution - Modular Arithmetic	O(n)	O(1)	Use modular arithmetic to directly calculate minimum operations needed

Brute Force - Try All Combinations — Algorithm Steps

Step 1: Calculate current sum
Step 2: Try all reduction combinations
Step 3: Find minimum operations needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Sum

Add all array elements

Find Remainder

sum % k gives excess amount

Result

Remainder is minimum operations needed

Code -

solution.c — C

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

int solution(int* nums, int numsSize, int k) {
    long long currentSum = 0;
    for (int i = 0; i < numsSize; i++) {
        currentSum += nums[i];
    }
    int remainder = currentSum % k;
    if (remainder == 0) {
        return 0;
    }
    return remainder;
}

int main() {
    char line[2000000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int* nums = malloc(100000 * sizeof(int));
    int numsSize = 0;
    
    char* ptr = line;
    while (*ptr && *ptr != '[') ptr++; // find opening bracket
    ptr++; // skip opening bracket
    
    char* start = ptr;
    while (*ptr && *ptr != ']') {
        if (*ptr == ',' || *ptr == ']') {
            char temp = *ptr;
            *ptr = '\0';
            nums[numsSize++] = atoi(start);
            *ptr = temp;
            if (*ptr == ',') {
                ptr++;
                while (*ptr == ' ') ptr++; // skip spaces
                start = ptr;
            }
        } else {
            ptr++;
        }
    }
    
    // Handle last number if we hit the closing bracket
    if (ptr > start && *(ptr-1) != ',') {
        nums[numsSize++] = atoi(start);
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    free(nums);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k^n)

For each element, we try k different reduction amounts

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

28.3K Views

Medium Frequency

~8 min Avg. Time

856 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 - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler