모든 챌린지
보통 0명 해결 정답률 0%

Champernowne Digits

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

배우게 될 내용

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

문제

번역본 보기

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.

제약 조건

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

예시

예시 1
입력:
positions = [1, 9, 10, 11]

예상 출력:
expected = [1, 9, 1, 0]
입력:
std::vector<long long> positions = {1, 9, 10, 11};

예상 출력:
std::vector<long long> expected = {1, 9, 1, 0};
입력:
long[] positions = new long[] {1, 9, 10, 11};

예상 출력:
long[] expected = new long[] {1, 9, 1, 0};

설명

The string starts 1 2 3 4 5 6 7 8 9 1 0 1 1, so the digits are [1, 9, 1, 0].

예시 2
입력:
positions = [15, 190]

예상 출력:
expected = [2, 1]
입력:
std::vector<long long> positions = {15, 190};

예상 출력:
std::vector<long long> expected = {2, 1};
입력:
long[] positions = new long[] {15, 190};

예상 출력:
long[] expected = new long[] {2, 1};

설명

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].

접근 방법

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

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

힌트 2

Subtract whole blocks until the position falls inside one.

힌트 3

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

예상 복잡도

O(m × log P) time for m positions, O(m) extra space

참고 자료

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.