Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

1694. Make Sum Divisible by P

My accepted Python solution to LeetCode problem 1694, Make Sum Divisible by P, running in 67ms.

  • Difficulty: Medium
  • Python
  • Runtime 67ms
  • Memory 37.4MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 67ms, memory 37.4MB, accepted 2025-12-30.

python
class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        total = sum(nums)
        target = total % p
        
        if target == 0:
            return 0
        
        # Need to remove a subarray with sum % p == target
        # prefix_sum[j] - prefix_sum[i] ≡ target (mod p)
        # prefix_sum[j] - target ≡ prefix_sum[i] (mod p)
        
        prefix_mod = {0: -1}
        curr_sum = 0
        min_len = len(nums)
        
        for i, num in enumerate(nums):
            curr_sum = (curr_sum + num) % p
            need = (curr_sum - target) % p
            
            if need in prefix_mod:
                min_len = min(min_len, i - prefix_mod[need])
            
            prefix_mod[curr_sum] = i
        
        return min_len if min_len < len(nums) else -1

Source