Alle Herausforderungen
Mittel 0 gelöst 0% Erfolgsquote

Champernowne-Ziffern

Finde die Ziffern an bestimmten Positionen der Ziffernfolge 123456789101112..., die durch Aneinanderreihen der natürlichen Zahlen entsteht.

Das lernst du

  • Die Stellen zählen, die Zahlen jeder Länge belegen
  • Aus einer Position die Zahl und die Ziffer bestimmen
  • Sicher mit 64-Bit-Arithmetik rechnen

Problem

Schreibe die positiven ganzen Zahlen hintereinander: 123456789101112131415... An Position 1 steht die 1, an Position 10 die 1 der Zahl 10 und an Position 11 die 0 der Zahl 10. Finde für jede angefragte Position die Ziffer, die dort steht. Die Positionen sind viel zu groß, um die Folge tatsächlich als String aufzubauen. Überspringe stattdessen ganze Blöcke von Zahlen mit gleicher Stellenzahl (9 einstellige, 90 zweistellige, 900 dreistellige Zahlen, ...).

Implementiere champernowne_digits(positions).

Eingabe

positions: Positionen in der Ziffernfolge, gezählt ab 1.

Ausgabe

Gib die Ziffer an jeder Position zurück, in derselben Reihenfolge wie in der Eingabe. Für eine leere Eingabe gib eine leere Liste zurück.

Einschränkungen

0 ≤ positions.length ≤ 100; 1 ≤ position ≤ 10^15

Beispiele

Beispiel 1
Eingabe:
positions = [1, 9, 10, 11]

Erwartete Ausgabe:
expected = [1, 9, 1, 0]
Eingabe:
std::vector<long long> positions = {1, 9, 10, 11};

Erwartete Ausgabe:
std::vector<long long> expected = {1, 9, 1, 0};
Eingabe:
long[] positions = new long[] {1, 9, 10, 11};

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

Erläuterung

Die Folge beginnt mit 1 2 3 4 5 6 7 8 9 1 0 1 1, die Ziffern sind also [1, 9, 1, 0].

Beispiel 2
Eingabe:
positions = [15, 190]

Erwartete Ausgabe:
expected = [2, 1]
Eingabe:
std::vector<long long> positions = {15, 190};

Erwartete Ausgabe:
std::vector<long long> expected = {2, 1};
Eingabe:
long[] positions = new long[] {15, 190};

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

Erläuterung

Position 15 ist die 2 der Zahl 12. Die Positionen 10 bis 189 enthalten die Zahlen 10 bis 99, also ist 190 die erste Ziffer von 100: [2, 1].

So gehst du vor

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

Hinweis 1

Die Zahlen mit d Stellen belegen insgesamt 9 × 10^(d − 1) × d Positionen.

Hinweis 2

Ziehe ganze Blöcke ab, bis die Position in einen Block fällt.

Hinweis 3

Innerhalb des Blocks sagt dir (position − 1) / d, welche Zahl es ist, und (position − 1) % d, welche Ziffer.

Erwartete Komplexität

Zeit O(m × log P) bei m Positionen, zusätzlicher Speicher O(m)

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.