Count Winning Pairings - 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 count the number of different winning pairings whose sum equals a power of two.
  • What input is provided?
    • An array of integers star_power.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a dictionary to count occurrences of each star power, then iterate through possible pairs and count those that sum to a power of two.

1) Create a list `powers_of_two` containing all powers of two up to `2^21`.
2) Use a dictionary `count` to store the frequency of each star power.
3) Iterate through `star_power`, and for each value, find the complement that would sum to a power of two.
   - Update the total pairs count.
4) Return the total pairs modulo `10^9 + 7`.

⚠️ Common Mistakes

• Not handling pairs with the same star power correctly.

I-mplement

def count_winning_pairings(star_power):
    MOD = 10**9 + 7
    powers_of_two = [2 ** i for i in range(22)]  # Compute powers of 2
    count = {}
    total_pairs = 0

    for value in star_power:
        for power in powers_of_two:
            complement = power - value
            if complement in count:
                total_pairs = (total_pairs + count[complement]) % MOD
        
        if value in count:
            count[value] += 1
        else:
            count[value] = 1

    return total_pairs