DDSA Solutions

1590. Make Sum Divisible by P

MediumView on LeetCode
ArrayHash TablePrefix Sum
Time: O(n)
Space: O(n)

Problem Overview

Find shortest subarray to remove to make sum divisible by p.

Intuition

Find shortest subarray to remove to make sum divisible by p. Use prefix sums and modular arithmetic. Track last seen index for each prefix mod.

Algorithm

  1. 1Need = total_sum % p. If need == 0: return 0.
  2. 2Prefix sums mod p. For each right index r: find leftmost l where (prefix[r]-prefix[l])%p == need. Answer = r-l.
  3. 3Map: mod -> last index.

Common Pitfalls

  • •Target subarray sum mod p == need. Use map of prefix_mod to index. Minimize r-l > 0.
1590.cs
C#
// Approach: Prefix sums mod p with a HashMap to find shortest subarray whose removal makes total divisible by p.
// Time: O(n) Space: O(n)

public class Solution
{
    public int MinSubarray(int[] nums, int p)
    {
        long sum = 0;
        foreach (int val in nums)
            sum = sum + val;

        int remainder = (int)(sum % p);
        if (remainder == 0)
            return 0;

        int ans = nums.Length;
        int prefix = 0;
        Dictionary<int, int> prefixToIndex = new Dictionary<int, int>();
        prefixToIndex[0] = -1;

        for (int i = 0; i < nums.Length; ++i)
        {
            prefix += nums[i];
            prefix %= p;
            int target = (prefix - remainder + p) % p;
            if (prefixToIndex.ContainsKey(target))
                ans = Math.Min(ans, i - prefixToIndex[target]);
            prefixToIndex[prefix] = i;
        }

        return ans == nums.Length ? -1 : ans;
    }
}
Was this solution helpful?

Related Problems