CSES-Digit Queries problem need idea

Hi, I have been trying to solve this problem for quite a time but could not generate any better idea.
It would be very helpful if someone tell me how to solve it, give some resources to solve this problem and provide me some similar problems
Problem

1 Like

Hi, This is my approach.

Given an index and we need to find the digit value, instead we will find the value X that this digit will fall into (like instead of finding digit 2 let’s find out 102… ). Before finding this value X let’s find out the size of this value. (i.e. is this value 2 digit or 3 digit …).

So… Inorder to find the size of that value consider all digit values and the total no of digits in those digit category i.e. (1 digit values are 1, 2, … 9 → total no of digits in this 1 digited no’s are (9 * 1) ), (2 digit values are 10, 11, 12, … 99 → total no of digits in this 2 digited no’s are (90 * 2)) . So in this way we can find out in which sized category the value X will fall into.

Now we have known that the value X that we have to find lies some where in some specific size digited numbers (like it will be in 100, 101, … 999 if it is 3 sized) . Now we have to find that value X and i did binary search for that . After we gets the value of X we can easily find the digit that we have to find.

You can refer to my code

or You can directly binary search from 1 to 1e18.

6 Likes

Thank you so much for this detailed solution.

You can have a look at a mathematical approach along with its proof.
here: https://artemlos.net/docs/2014/01/MathExploration.pdf

1 Like

You can refer to my repository on github, where i have solved many of the CSES problems & am still updating those solutions. I would also be giving a small editorial of the general idea about the solution approach:
Link : https://github.com/MojoAlpha/CSES-Problemset

1 Like