Coverage for blog/dsa/leetcode/divide_players/__init__.py: 52%

1import pytest 

2 

3 

4# start snippet solution 

5class Solution: 

6 

7 # NOTE: Skill has positive elements and even length. 

8 def dividePlayers(self, skill: list[int]) -> int: 

9 

10 s, n = sum(skill), len(skill) 

11 n2 = n // 2 

12 

13 # NOTE: Must be divisible by n. 

14 if s % n2: 

15 return -1 

16 

17 # NOTE: Memo maps completions to their index in ``skill``. 

18 target = s // n2 

19 memo: dict[int, int] = {} 

20 

21 out = 0 

22 for val in skill: 

23 

24 if (diff := target - val) <= 0: 

25 return -1 

26 elif val in memo: 

27 memo[val] -= 1 

28 out += val * diff 

29 

30 if memo[val] == 0: 

31 memo.pop(val) 

32 

33 elif diff not in memo: 

34 memo[diff] = 1 

35 else: 

36 memo[diff] += 1 

37 

38 if memo: 

39 return -1 

40 

41 return out 

42 # end snippet solution 

43 

44 

45# start snippet sort 

46class SolutionSort: 

47 

48 def dividePlayers(self, skill: list[int]) -> int: 

49 

50 skill.sort() 

51 n = len(skill) 

52 target = skill[0] + skill[n - 1] 

53 

54 out = 0 

55 for k in range(n // 2): 

56 j = n - 1 - k 

57 a, b = skill[k], skill[j] 

58 

59 if a + b != target: 

60 return -1 

61 

62 out += a * b 

63 

64 return out 

65 # end snippet sort 

66 

67 

68@pytest.fixture 

69def solution(): 

70 return SolutionSort() 

71 

72 

73@pytest.mark.parametrize( 

74 "question, answer", 

75 ( 

76 ([3, 2, 5, 1, 3, 4], 22), 

77 ([3, 4], 12), 

78 ([1, 1, 2, 3], -1), 

79 ([2, 1, 5, 2], -1), 

80 ([2, 3, 4, 2, 5, 5], 32), 

81 ([10, 14, 16, 15, 9, 4, 4, 4], -1), 

82 ), 

83) 

84def test_solution( 

85 solution: Solution, 

86 question: list[int], 

87 answer: int, 

88): 

89 

90 answer_computed = solution.dividePlayers(question) 

91 assert answer == answer_computed