Mittel 0 gelöst 0% Erfolgsquote

Champernowne Digits

Find digits at given positions of the string 123456789101112... made by writing out the counting numbers.

Das lernst du

  • Count digits used by numbers of each length
  • Locate a number and digit from a position
  • Use 64-bit arithmetic safely

Problem

Übersetzung anzeigen

Write the positive integers one after another: 123456789101112131415... Position 1 holds 1, position 10 holds the 1 of 10, position 11 the 0 of 10. For each requested position, find the digit there. The positions go far past what you could build as a string: skip whole blocks of numbers with the same number of digits (9 one-digit numbers, 90 two-digit numbers, 900 three-digit numbers, ...).

Implement champernowne_digits(positions).

Input

positions: Positions in the digit string, counting from 1.

Output

Return the digit at each position, in the same order as the input. An empty input returns an empty list.

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

The string starts 1 2 3 4 5 6 7 8 9 1 0 1 1, so the digits are [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 is the 2 of 12. Positions 10 to 189 hold 10 to 99, so 190 is the first digit of 100: [2, 1].

So gehst du vor

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

Hinweis 1

Numbers with d digits take 9 × 10^(d − 1) × d positions in total.

Hinweis 2

Subtract whole blocks until the position falls inside one.

Hinweis 3

Within the block, (position − 1) / d tells you which number and (position − 1) % d which digit.

Erwartete Komplexität

O(m × log P) time for m positions, O(m) 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.