# Daily Problem 10/03/2024: Make Sum Divisible by `p`

Find a maximal subarray of an integer array whose modulus by

`p`

is `0`

.
The full problem may be found on leetcode.

## Analysis

The trivial solution is to look at every possible sub-array, which will have quadratic time complexity. This solution looks like

```
class SolutionTrivial:
def minSubarray(self, nums: list[int], p: int) -> int:
= sum(nums)
total = len(nums)
n = total % p
total_remainder if total_remainder == 0:
return 0
= n
best for k in range(n):
= 0
s for j in range(k, n):
+= nums[j]
s if s % p == total_remainder and j + 1 - k < best:
= j + 1 - k
best
return best
```

and (obviously) exceeded the allowed runtime.

A better solution is to remember calculate the sums modulus and check if the complimenting modulus could be found. I got close, but I eventually confused myself into oblivion and decided to read the editorial.

## Solution

The editorial presented a solution with linear time complexity. This solution used the ‘Two Sum’ memoization trick. I found a few optimizations that can be made:

`needed`

does not need to be`(s - target + p) % p`

since the modulus is commutative,`target`

can be computed just by taking the modulus of the sum.

In the end, this solution performed very well, beating \(89\%\) of submissions in its best run.

```
class Solution:
def minSubarray(self, nums: list[int], p: int) -> int:
= sum(nums), len(nums)
total, n
= total % p
target if target == 0:
return 0
= n
out = {0: -1}
mem = 0
s
for k in range(n):
= (s + nums[k]) % p
s = (s - target) % p
needed if needed in mem:
= min(out, k - mem[needed])
out
= k
mem[s]
return -1 if out == n else out
```