Overview

Given a list of winning numbers and a list of lottery ticket numbers you hold, this problem asks you to count the number of winning lottery tickets.

Analysis

The Essence of the Problem

This problem can be reduced to “counting the number of common elements between two lists.”

Issues with the Naive Approach

The simplest method is to search through the winning number list \(A\) from the beginning for each lottery ticket number \(B_j\) you hold.

# Naive approach (risk of TLE)
count = 0
for b in B:
    for a in A:
        if b == a:
            count += 1
            break

With this method, for each of the \(M\) lottery tickets, we check up to \(K\) winning numbers in the worst case, resulting in a time complexity of \(O(K \times M)\).

When both \(K\) and \(M\) are at their maximum of \(10^5\), we would need \(10^5 \times 10^5 = 10^{10}\) comparisons, which will not finish within the time limit (TLE).

Solution: Using a Set

Using Python’s set, we can check whether an element is contained in the set in average \(O(1)\) time.

By storing the winning numbers in a set, we can quickly determine whether each lottery ticket number is a winner.

Concrete Example

Winning numbers A = {5, 12, 8} (stored as a set)
Your tickets    B = [3, 12, 7, 5]

- Is 3 in A? → No
- Is 12 in A? → Yes (count + 1)
- Is 7 in A? → No
- Is 5 in A? → Yes (count + 1)

Answer: 2

Algorithm

1. Read the \(K\) winning numbers and store them as a set
2. Read the \(M\) lottery ticket numbers you hold
3. For each lottery ticket number, check if it’s contained in the winning numbers set, and increment the count if it is
4. Output the count

K, M = map(int, input().split())
A = set(map(int, input().split()))  # Store winning numbers in a set
B = list(map(int, input().split()))

count = sum(1 for b in B if b in A)  # Count the number of b's contained in A
print(count)

Complexity

• Time Complexity: \(O(K + M)\)
  • Building the set takes \(O(K)\)
  • For each of the \(M\) elements, membership check in the set takes average \(O(1)\), for a total of \(O(M)\)
• Space Complexity: \(O(K + M)\)
  • \(O(K)\) for the set storing winning numbers
  • \(O(M)\) for the list storing your ticket numbers

Implementation Notes

• Choose which side to make a set: Make the winning numbers \(A\) a set, and keep the ticket numbers \(B\) as a list. Making the side being searched into a set enables faster lookups.

• Using sum with a generator expression: sum(1 for b in B if b in A) is a Pythonic way to count the number of elements satisfying a condition.

• Alternative solution: You can also use set intersection like len(set(A) & set(B)). However, note that if \(B\) contains duplicates, the result will differ (in this problem, all elements in \(B\) are distinct, so the results are the same).

  Source Code

K, M = map(int, input().split())
A = set(map(int, input().split()))
B = list(map(int, input().split()))

count = sum(1 for b in B if b in A)
print(count)

---

This editorial was generated by claude4.5opus.