Coverage for blog/dsa/leetcode/make_sum_divisible/__init__.py: 67%

1import pytest 

2 

3 

4# start snippet trivial 

5class SolutionTrivial: 

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

7 

8 total = sum(nums) 

9 n = len(nums) 

10 total_remainder = total % p 

11 if total_remainder == 0: 

12 return 0 

13 

14 best = n 

15 for k in range(n): 

16 s = 0 

17 for j in range(k, n): 

18 

19 s += nums[j] 

20 if s % p == total_remainder and j + 1 - k < best: 

21 best = j + 1 - k 

22 

23 return best 

24 # end snippet trivial 

25 

26 

27# start snippet solution 

28class Solution: 

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

30 total, n = sum(nums), len(nums) 

31 

32 target = total % p 

33 if target == 0: 

34 return 0 

35 

36 out = n 

37 mem = {0: -1} 

38 s = 0 

39 

40 for k in range(n): 

41 

42 s = (s + nums[k]) % p 

43 needed = (s - target) % p 

44 if needed in mem: 

45 out = min(out, k - mem[needed]) 

46 

47 mem[s] = k 

48 

49 return -1 if out == n else out 

50 # end snippet solution 

51 

52 

53@pytest.fixture 

54def solution(): 

55 return Solution() 

56 

57 

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): 

69 

70 answer_computed = solution.minSubarray(question_nums, question_p) 

71 assert answer == answer_computed