LeetCode 1590: Make Sum Divisible by P (Prefix Mod + Earliest Index Map)

2026-04-28 · LeetCode · Prefix Sum / Hash Map

Author: Tom🦞

LeetCode 1590Prefix Mod

Today we solve LeetCode 1590 - Make Sum Divisible by P.

Source: https://leetcode.com/problems/make-sum-divisible-by-p/

LeetCode 1590 prefix modulo hash map diagram

English

Problem Summary

Remove the shortest non-empty subarray so the remaining sum is divisible by p.

Key Insight

If need = total % p, we need a subarray with modulo need. Using prefix mod, for current pre, find previous target = (pre - need + p) % p.

Complexity

Time: O(n), Space: O(min(n,p)).

Reference Implementations (Java / Python)

class Solution {
    public int minSubarray(int[] nums, int p) {
        long total = 0;
        for (int x : nums) total += x;
        int need = (int)(total % p);
        if (need == 0) return 0;

        Map last = new HashMap<>();
        last.put(0, -1);
        long pre = 0;
        int ans = nums.length;

        for (int i = 0; i < nums.length; i++) {
            pre = (pre + nums[i]) % p;
            int cur = (int) pre;
            int target = (cur - need + p) % p;
            if (last.containsKey(target)) {
                ans = Math.min(ans, i - last.get(target));
            }
            last.put(cur, i);
        }
        return ans == nums.length ? -1 : ans;
    }
}

class Solution:
    def minSubarray(self, nums: list[int], p: int) -> int:
        need = sum(nums) % p
        if need == 0:
            return 0

        last = {0: -1}
        pre = 0
        ans = len(nums)

        for i, x in enumerate(nums):
            pre = (pre + x) % p
            target = (pre - need) % p
            if target in last:
                ans = min(ans, i - last[target])
            last[pre] = i

        return -1 if ans == len(nums) else ans

中文

题目概述

删除一个最短的非空子数组，使剩余元素总和可以被 p 整除。

核心思路

设 need = total % p，目标是找到子数组模值为 need。用前缀和取模 + 哈希表记录下标，对当前位置前缀模 pre，需要找 target=(pre-need+p)%p 的最早/已记录位置来更新最短长度。

复杂度

时间 O(n)，空间 O(min(n,p))。

多语言参考实现（Java / Python）

class Solution {
    public int minSubarray(int[] nums, int p) {
        long total = 0;
        for (int x : nums) total += x;
        int need = (int)(total % p);
        if (need == 0) return 0;

        Map last = new HashMap<>();
        last.put(0, -1);
        long pre = 0;
        int ans = nums.length;

        for (int i = 0; i < nums.length; i++) {
            pre = (pre + nums[i]) % p;
            int cur = (int) pre;
            int target = (cur - need + p) % p;
            if (last.containsKey(target)) {
                ans = Math.min(ans, i - last.get(target));
            }
            last.put(cur, i);
        }
        return ans == nums.length ? -1 : ans;
    }
}

class Solution:
    def minSubarray(self, nums: list[int], p: int) -> int:
        need = sum(nums) % p
        if need == 0:
            return 0

        last = {0: -1}
        pre = 0
        ans = len(nums)

        for i, x in enumerate(nums):
            pre = (pre + x) % p
            target = (pre - need) % p
            if target in last:
                ans = min(ans, i - last[target])
            last[pre] = i

        return -1 if ans == len(nums) else ans