Leetcode solution (1590): make array sum divisible by P (Python)

subject ：​ ​ The original title is link ​​（ secondary ）

label ： Array 、 Hashtable 、 mathematics

solution

Time complexity

Spatial complexity

Execution time

Ans 1 (Python)

O ( N )

O ( N )

312ms (38%)

Ans 2 (Python)

Ans 3 (Python)

Solution 1 ：

class Solution:

 def minSubarray(self, nums: List[int], p: int) -> int:

 # Calculate the remainder

 # O(N)

 total = sum(nums)

 surplus = total % p

 # print(" Target remainder :", surplus)



 # The processing remainder is 0 The situation of

 if surplus == 0:

 return 0



 # Prefix hash table

 hashmap = {}



 ans = -1



 # Calculate prefix remainder

 # O(N)

 last = 0

 hashmap[0] = -1

 for i, num in enumerate(nums):

 last += num

 last %= p

 hashmap[last] = i



 # Check whether it constitutes the target remainder

 aim_val = (p + last - surplus) % p

 if aim_val in hashmap:

 now = i - hashmap[aim_val]

 if ans == -1 or ans > now:

 ans = now



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


1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.