4022. K-th Digit in Infinite String

You are given an integer k.

An infinite string is formed by concatenating the decimal representations of the positive integers, without separators.

For every nonnegative integer b, block b contains the positive integers from 10 * b through 10 * b + 9. The integers in each block are appended as follows:

• If b is even, append the integers in increasing order.
• If b is odd, append the integers in decreasing order.

Therefore, the string starts with the integers 1 through 9, followed by 19 through 10, then 20 through 29, then 39 through 30, and so on.

Return the k^th digit (1-indexed) of this string.

class Solution {
public:
    int kthDigit(long long k) {
        long long remain = k;
        long long digit = 1, base = 0;
        long long count = 9;
        while(remain > count) {
            remain -= count;
            digit++;
            base = digit == 2 ? 1 : base * 10;
            count = (long long)9 * digit * base * 10;
        }
        if(digit == 1) return remain;
        remain--;
        long long block = base + remain / (digit * 10);
        long long inside = remain % (digit * 10);
        long long idx = inside / digit;
        long long pos = inside % digit;
        long long num = block * 10 + (block & 1 ? 9 - idx : idx);
        return to_string(num)[pos] - '0';
    }
};