Minimum Sum After Divisible Sum Deletions - Solution & Explanation

Problem Overview: You are given an array and can delete subarrays whose total sum is divisible by k. The goal is to perform deletions so the remaining array sum is as small as possible. The challenge is identifying which segments to remove while avoiding overlapping choices that reduce the final benefit.

Approach 1: Brute Force Subarray Enumeration (O(n²) time, O(1) space)

Compute the sum of every possible subarray and check whether it is divisible by k. For each valid subarray, simulate removing it and track the remaining sum. This requires nested loops to enumerate (i, j) boundaries and repeated sum calculations. While straightforward, it quickly becomes too slow for large arrays because the number of candidate subarrays grows quadratically. This approach mainly helps build intuition about how divisible subarrays affect the final sum.

Approach 2: Prefix Sum + Hash Map Optimization (O(n) time, O(n) space)

The key observation: if two prefix sums have the same remainder when divided by k, the subarray between them has a sum divisible by k. Maintain a running prefixSum and compute prefixSum % k. Use a hash map to store the earliest occurrence of each remainder. When the same remainder appears again, the segment between indices forms a removable subarray. Track the maximum removable sum or the optimal deletion configuration while scanning once through the array.

This method converts the problem into a remainder-matching problem using a prefix sum pattern. The hash table enables constant-time lookups for previously seen remainders, making it efficient for large inputs. Many interview problems with divisibility constraints follow this same pattern with hash tables and modular arithmetic.

Approach 3: Dynamic Programming with Prefix Tracking (O(n) time, O(n) space)

Dynamic programming can track the best achievable removed sum up to each index. Maintain DP states representing the maximum removable sum ending at or before the current index. When a divisible subarray is detected using prefix remainders, update the DP value by combining the current segment with the best previous configuration. This prevents overlapping deletions and guarantees the optimal result. The DP state transitions rely on the same remainder grouping used in the prefix sum method, tying together ideas from dynamic programming and modular prefix sums.

Recommended for interviews: The prefix sum + hash map approach is the expected solution. Interviewers want to see that you recognize the remainder property of divisible subarrays and reduce the search from O(n²) to O(n). Mentioning the brute force approach first shows you understand the problem space, but implementing the prefix remainder technique demonstrates strong algorithmic pattern recognition.