digit-queries

Digit Queries

CSES medium

Consider the infinite string formed by concatenating all positive integers in order:

[ 1234567891011121314]

You are given \(q\) queries. For each query, you are given a position \(k\) (1-indexed) in this infinite string. Your task is to output the digit at position \(k\).

Constraints:

\(1 \le q \le 1000\)
\(1 \le k \le 10^{18}\)

Solution

We cannot actually build the infinite string (or even a large prefix of length \(10^{18}\)). Instead, we reason about blocks of numbers with the same digit length.

1. Group numbers by digit length

1-digit numbers: from 1 to 9
- Count of numbers: \(9\)
- Digits contributed: \(9 \cdot 1\)
2-digit numbers: from 10 to 99
- Count: \(90\)
- Digits: \(90 \cdot 2 = 180\)
3-digit numbers: from 100 to 999
- Count: \(900\)
- Digits: \(900 \cdot 3 = 2700\)

In general, for \(d\)-digit numbers:

First \(d\)-digit number is \(10^{d-1}\)
There are \(9 \cdot 10^{d-1}\) such numbers
They contribute \(9 \cdot d \cdot 10^{d-1}\) digits in total

For a query position \(k\):

Start with digit length \(d = 1\) and base = 1 (which is \(10^{d-1}\)).
Let block_len = 9 * base * d = total digits in the \(d\)-digit block.
If k > block_len, subtract this block and move to the next:
- k -= block_len
- d++, base *= 10 (now looking at \((d+1)\)-digit numbers)
Stop when k falls inside the current block (i.e., k <= block_len).

Now we know:

The digit we want is in the block of d-digit numbers,
starting from start = base = 10^{d-1}.

2. Identify the exact number and digit

Inside this \(d\)-digit block:

Consider 0-based indexing for convenience:
- k0 = k - 1 (0-based index within this block)
- index_of_number = k0 / d (integer division)
- index_in_number = k0 % d (which digit in that number)
The actual number is:
- num = start + index_of_number
To get the specific digit:
- Convert num to string and take the index_in_number-th character, or
- Use integer operations to pick the correct digit.

Given constraints, using std::string conversion is perfectly fine.

3. Complexity

For each query:

We increase d at most up to 17 (since \(k \le 10^{18}\)), so the loop over digit lengths is O(1).
All operations are on long long and small strings.

Total complexity: \(O(q)\).

Digit block logic (per query)

Find \(d\) such that \(k\) lies in the block of \(d\)-digit numbers:
- Repeatedly do
  - block_len = 9 * base * d
  - if (k > block_len) { k -= block_len; d++; base *= 10; }
Then:
- k0 = k - 1
- index_of_number = k0 / d
- index_in_number = k0 % d
- num = base + index_of_number
- Answer = the index_in_number-th digit of num.

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> q;

    while (q--) {
        long long k;
        cin >> k;

        long long d = 1;       // current digit length
        long long base = 1;    // 10^(d-1)

        // Step 1: find the block (digit length d) that contains position k
        while (true) {
            long long count_numbers = 9 * base;      // how many d-digit numbers
            long long block_len = count_numbers * d; // total digits in this block

            if (k > block_len) {
                k -= block_len;
                d++;
                base *= 10;
            } else {
                break; // k is inside this block
            }
        }

        // Step 2: find the exact number and digit within this d-digit block
        long long k0 = k - 1;                 // 0-based index within this block
        long long index_of_number = k0 / d;   // which number in this block
        long long index_in_number = k0 % d;   // which digit inside that number

        long long num = base + index_of_number;

        // Convert number to string and pick the right digit
        string s = to_string(num);
        char answer_digit = s[index_in_number];

        cout << answer_digit << endl;
    }

    return 0;
}

Watch out for overflow

Use long long for k, base, and block_len.
For this problem, \(d\) never needs to exceed 17 when \(k \le 10^{18}\), so 9 * base * d safely fits in long long.