Make Sum Divisible by P - Practice Coding Problems

Make Sum Divisible by P - Problem

Given an array of positive integers nums, remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible by p. It is not allowed to remove the whole array.

Return the length of the smallest subarray that you need to remove, or -1 if it's impossible.

A subarray is defined as a contiguous block of elements in the array.

Input & Output

Example 1 — Basic Removal

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

› Output: 1

💡 Note: Total sum is 10. We need sum divisible by 6. Remove subarray [4] (length 1) to get [3,1,2] with sum 6, which is divisible by 6.

Example 2 — No Removal Needed

$ Input: nums = [6,3,5,2], p = 9

› Output: 2

💡 Note: Total sum is 16. Remove subarray [5,2] (length 2) to get [6,3] with sum 9, which is divisible by 9.

Example 3 — Impossible Case

$ Input: nums = [1,2,3], p = 3

› Output: 0

💡 Note: Total sum is 6, which is already divisible by 3. No removal needed, return 0.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array [3,1,4,2] and divisor p=6

Process

Find shortest subarray with remainder 4

Output

Remove 1 element to make remaining sum divisible

Key Takeaway

🎯 Key Insight: Use prefix sums and hash map to efficiently find the shortest subarray whose remainder matches the total remainder

Asked in

F Facebook 15 G Google 12 a Amazon 8

The key insight is that we need to find the shortest subarray whose sum has the same remainder as the total sum modulo p. The optimal approach uses prefix sums with hash map to track remainders and find the minimum length subarray in O(n) time. Time: O(n), Space: O(min(n,p))

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(1)	Try all possible subarrays and check if removing each makes the remainder divisible by p
Prefix Sum with Hash Map	O(n)	O(min(n,p))	Use prefix sums and hash map to efficiently find the shortest subarray with target remainder

Brute Force — Algorithm Steps

Calculate total sum modulo p
Try all subarrays from length 0 to n-1
For each subarray, check if (total - subarray_sum) % p == 0
Return minimum length found

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Total

Sum all elements and find remainder

Try Subarrays

Check each contiguous subarray

Find Minimum

Return shortest valid subarray length

Code -

solution.c — C

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

int solution(int* nums, int numsSize, int p) {
    long long total = 0;
    for (int i = 0; i < numsSize; i++) {
        total += nums[i];
    }
    
    if (total % p == 0) {
        return 0;
    }
    
    long long targetRemainder = total % p;
    int minLen = numsSize;
    
    for (int i = 0; i < numsSize; i++) {
        long long currentSum = 0;
        for (int j = i; j < numsSize; j++) {
            currentSum += nums[j];
            if (currentSum % p == targetRemainder) {
                int len = j - i + 1;
                if (len < minLen) {
                    minLen = len;
                }
            }
        }
    }
    
    return minLen < numsSize ? minLen : -1;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int p;
    scanf("%d", &p);
    
    int result = solution(nums, numsSize, p);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops: start position, end position, and sum calculation

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few variables to track minimum length and current sum

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 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 — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler