Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Ticket Lottery Winners

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

Das lernst du

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

Problem

Übersetzung anzeigen

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.

Einschränkungen

1 ≤ len(winning) ≤ 10

0 ≤ number of tickets ≤ 5,000

1 ≤ every number ≤ 99

Beispiele

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

Erwartete Ausgabe:
expected = [1, 1, 1, 1]
Eingabe:
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}
};

Erwartete Ausgabe:
std::vector<long long> expected = {1, 1, 1, 1};
Eingabe:
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}
};

Erwartete Ausgabe:
long[] expected = new long[] {1, 1, 1, 1};

Erläuterung

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

Beispiel 2
Eingabe:
winning = [7, 8]
tickets = [
    [8, 7],
    [7, 1],
    [1, 7]
]

Erwartete Ausgabe:
expected = [0, 2, 1]
Eingabe:
std::vector<long long> winning = {7, 8};
std::vector<std::vector<long long>> tickets = {
    {8, 7},
    {7, 1},
    {1, 7}
};

Erwartete Ausgabe:
std::vector<long long> expected = {0, 2, 1};
Eingabe:
long[] winning = new long[] {7, 8};
long[][] tickets = new long[][] {
    new long[] {8, 7},
    new long[] {7, 1},
    new long[] {1, 7}
};

Erwartete Ausgabe:
long[] expected = new long[] {0, 2, 1};

Erläuterung

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

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

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

Hinweis 2

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

Hinweis 3

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

Erwartete Komplexität

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

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.