Pair Contestants - codepath/compsci_guides GitHub Wiki
U-nderstand
Understand what the interviewer is asking for by using test cases and questions about the problem.
- Q
- What is the desired outcome?
- To determine if it is possible to pair all contestants such that the sum of the scores of each pair is divisible by
k
.
- To determine if it is possible to pair all contestants such that the sum of the scores of each pair is divisible by
- What input is provided?
- An array of integers
scores
and an integerk
.
- An array of integers
- What is the desired outcome?
P-lan
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Use a dictionary to count the remainders when dividing each score by k
, then check if valid pairs can be formed.
1) Create a dictionary `remainder_count` to store the frequency of each remainder when scores are divided by `k`.
2) Iterate over `scores` to populate the dictionary.
3) Check if valid pairs can be formed:
- For remainder `0`, the count must be even.
- For remainder `r`, the count must match the count of `k - r`.
4) If all checks pass, return `True`; otherwise, return `False`.
⚠️ Common Mistakes
- Not handling the case where
r
is half ofk
correctly.
I-mplement
def pair_contestants(scores, k):
remainder_count = {}
# Count the remainders
for score in scores:
remainder = score % k
if remainder in remainder_count:
remainder_count[remainder] += 1
else:
remainder_count[remainder] = 1
# Check pairs
for r in range(k):
if r == 0:
if remainder_count.get(r, 0) % 2 != 0:
return False
elif r * 2 == k:
if remainder_count.get(r, 0) % 2 != 0:
return False
else:
if remainder_count.get(r, 0) != remainder_count.get(k - r, 0):
return False
return True