Coverage for blog/dsa/leetcode/make_sum_divisible/__init__.py: 67%
39 statements
« prev ^ index » next coverage.py v7.6.12, created at 2025-02-20 16:23 +0000
« prev ^ index » next coverage.py v7.6.12, created at 2025-02-20 16:23 +0000
1import pytest
4# start snippet trivial
5class SolutionTrivial:
6 def minSubarray(self, nums: list[int], p: int) -> int:
8 total = sum(nums)
9 n = len(nums)
10 total_remainder = total % p
11 if total_remainder == 0:
12 return 0
14 best = n
15 for k in range(n):
16 s = 0
17 for j in range(k, n):
19 s += nums[j]
20 if s % p == total_remainder and j + 1 - k < best:
21 best = j + 1 - k
23 return best
24 # end snippet trivial
27# start snippet solution
28class Solution:
29 def minSubarray(self, nums: list[int], p: int) -> int:
30 total, n = sum(nums), len(nums)
32 target = total % p
33 if target == 0:
34 return 0
36 out = n
37 mem = {0: -1}
38 s = 0
40 for k in range(n):
42 s = (s + nums[k]) % p
43 needed = (s - target) % p
44 if needed in mem:
45 out = min(out, k - mem[needed])
47 mem[s] = k
49 return -1 if out == n else out
50 # end snippet solution
53@pytest.fixture
54def solution():
55 return Solution()
58@pytest.mark.parametrize(
59 "question_nums, question_p, answer",
60 (
61 ([3, 1, 4, 2], 6, 1),
62 ([6, 3, 5, 2], 9, 2),
63 ([1, 2, 3], 3, 0),
64 ),
65)
66def test_solution(
67 solution: SolutionTrivial, question_nums: list[int], question_p: int, answer: int
68):
70 answer_computed = solution.minSubarray(question_nums, question_p)
71 assert answer == answer_computed