Alle Herausforderungen
Mittel 1 gelöst 25.0% Erfolgsquote

Count Dice Sequences

Count ordered die-roll sequences with a given total.

Das lernst du

  • Build answers from smaller totals
  • Write a recurrence over the last die roll
  • Take results modulo a large prime

Problem

Übersetzung anzeigen

A standard die produces an integer from 1 through 6. Count all nonempty ordered sequences of outcomes whose sum is target. Different orders count separately. Return the count modulo 1,000,000,007.

Implement dice_combinations(target).

Input

target: The required sum of all rolls.

Output

Return the number of sequences modulo 1,000,000,007.

Einschränkungen

1 ≤ target ≤ 1,000,000. Taking a count modulo 1,000,000,007 means returning its remainder after division by that number.

Beispiele

Beispiel 1
Eingabe:
target = 2

Erwartete Ausgabe:
expected = 2
Eingabe:
long long target = 2;

Erwartete Ausgabe:
long long expected = 2;
Eingabe:
long target = 2;

Erwartete Ausgabe:
long expected = 2;

Erläuterung

The two sequences are [2] and [1, 1].

Beispiel 2
Eingabe:
target = 4

Erwartete Ausgabe:
expected = 8
Eingabe:
long long target = 4;

Erwartete Ausgabe:
long long expected = 8;
Eingabe:
long target = 4;

Erwartete Ausgabe:
long expected = 8;

Erläuterung

The sequences are [4], [1,3], [3,1], [2,2], [1,1,2], [1,2,1], [2,1,1], and [1,1,1,1].

So gehst du vor

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

Hinweis 1

Think of smaller sums as building blocks for the target.

Hinweis 2

Use a running count for each sum based on the previous six sums.

Hinweis 3

Be careful to apply the modulo at every addition and handle sums below 1 separately.

Erwartete Komplexität

O(target) time, O(target) 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.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 ННикита Python 973 ms - 5/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 1 vollständige Lösung unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.