Pair Contestants

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.
  • What input is provided?
    • An array of integers scores and an integer k.

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 of k 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