All challenges
Medium 0 solved 0% acceptance

Champernowne Digits

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

What you'll learn

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

Problem

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.

Constraints

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

Examples

Example 1
Input:
positions = [1, 9, 10, 11]

Expected output:
expected = [1, 9, 1, 0]
Input:
std::vector<long long> positions = {1, 9, 10, 11};

Expected output:
std::vector<long long> expected = {1, 9, 1, 0};
Input:
long[] positions = new long[] {1, 9, 10, 11};

Expected output:
long[] expected = new long[] {1, 9, 1, 0};

Explanation

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

Example 2
Input:
positions = [15, 190]

Expected output:
expected = [2, 1]
Input:
std::vector<long long> positions = {15, 190};

Expected output:
std::vector<long long> expected = {2, 1};
Input:
long[] positions = new long[] {15, 190};

Expected output:
long[] expected = new long[] {2, 1};

Explanation

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

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

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

Hint 2

Subtract whole blocks until the position falls inside one.

Hint 3

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

Expected complexity

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

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.