All challenges
Medium 0 solved 0% acceptance

Ticket Lottery Winners

Count how many lottery tickets matched 0, 1, 2, ... of the winning numbers.

What you'll learn

  • Use a set to test membership quickly
  • Count matches per ticket
  • Build a histogram of scores

Problem

A school fundraiser runs a number lottery. The draw picks some distinct winning numbers, and every ticket has the same amount of distinct numbers. The order of numbers on a ticket does not matter; a ticket's score is how many of its numbers are winning numbers. To set the prizes, the organizers need to know how many tickets reached each score.

Implement ticket_lottery(winning, tickets).

Input

winning: The distinct winning numbers.

tickets: The tickets; each row holds the distinct numbers on one ticket, with the same length as winning.

Output

Return a list of length len(winning) + 1 where position k is the number of tickets that matched exactly k winning numbers.

Constraints

1 ≤ len(winning) ≤ 10

0 ≤ number of tickets ≤ 5,000

1 ≤ every number ≤ 99

Examples

Example 1
Input:
winning = [3, 11, 20]
tickets = [
    [3, 11, 20],
    [20, 5, 7],
    [1, 2, 4],
    [11, 3, 9]
]

Expected output:
expected = [1, 1, 1, 1]
Input:
std::vector<long long> winning = {3, 11, 20};
std::vector<std::vector<long long>> tickets = {
    {3, 11, 20},
    {20, 5, 7},
    {1, 2, 4},
    {11, 3, 9}
};

Expected output:
std::vector<long long> expected = {1, 1, 1, 1};
Input:
long[] winning = new long[] {3, 11, 20};
long[][] tickets = new long[][] {
    new long[] {3, 11, 20},
    new long[] {20, 5, 7},
    new long[] {1, 2, 4},
    new long[] {11, 3, 9}
};

Expected output:
long[] expected = new long[] {1, 1, 1, 1};

Explanation

The tickets match 3, 1, 0 and 2 numbers, so each score from 0 to 3 happens once: [1, 1, 1, 1].

Example 2
Input:
winning = [7, 8]
tickets = [
    [8, 7],
    [7, 1],
    [1, 7]
]

Expected output:
expected = [0, 2, 1]
Input:
std::vector<long long> winning = {7, 8};
std::vector<std::vector<long long>> tickets = {
    {8, 7},
    {7, 1},
    {1, 7}
};

Expected output:
std::vector<long long> expected = {0, 2, 1};
Input:
long[] winning = new long[] {7, 8};
long[][] tickets = new long[][] {
    new long[] {8, 7},
    new long[] {7, 1},
    new long[] {1, 7}
};

Expected output:
long[] expected = new long[] {0, 2, 1};

Explanation

One ticket has both numbers (order does not matter) and two have one: [0, 2, 1].

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

Put the winning numbers in a set or a boolean array indexed by number.

Hint 2

Count matches on one ticket, then add 1 to that score's bucket.

Hint 3

The result has one more bucket than there are winning numbers.

Expected complexity

O(t × k) time, O(k) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.