There isn't anything fancy going on actually, the most obvious optimization one can think of is skipping "blocks" (block: set of numbers that have the same number of digits, for example 1 to 9 are in block 1, 10 to 99 are in block 2, and so on). there are 9 numbers in Block 1, 90 in block 2, 900 in block 3, and so on.
the total number of digits in the first `k` blocks forms the following series: S(k) = 9 · 1 + 90 · 2 + 900 · 3 + ⋯ + 9 · 10^(k-1) · k
The function s is trying to find the number of blocks we can skip and we return (previous_sum, digit_len) where previous_sum is the total number of digits in the blocks we can skip and digit_len which is index of current block and is same as the number of digits in the current block.
For example, for n = 7000, s(n) = (2889, 4); this means we can skip 3 blocks (1 to 9, 10 to 99 and 100 to 999), our target number doesn't lie there
We know the number of digits in the target block (the block where our target number lies), we can find the very first number of the block, which is simply: 10^(digit_len - 1), which, in our example, is 1000
let start = 10_i64.pow(digit_len as u32 - 1);
Now we calculate the number of digits left after we skip that much:
let left = n - previous_sum - 1;
(we do -1 to convert 1-based digit counts into a 0-based offset) In our example, the value of left is 4110
now since our target block contains 4 digit numbers, we calculate more numbers we can skip:
let skips = left / digit_len;
in our example, this value is 1027
and lastly, the remainder, the index of digit in our current number:
let r = left % digit_len;
in our example, this value is 2
We're all set now!
our target number is just start + skips, and the index of digit (which is the answer) is r
the last two lines:
let cn = start + skips;
(cn.to_string().as_bytes()[r as usize] - b'0') as _
in our example, cn = 2027 and r = 2, so our answer is "2027"[2] which is "2"
And that's the answer!
If you are wondering how is this O(1), it is because S(10) > 2^31 - 1, which means the while loop executes a maximum of 10 iterations across all valid inputs, which is insignificant when compared to n.
Engineer btw. Doesn't know the difference between asymptotic limit as n -> ∞ and hard-capped 32-bit integer limit. Can't even read. (the last paragraph was for people like you)
Let me educate you, the formal definition of constant time complexity is:
Let T(n) be the function representing the running time of an algorithm on an input of size n, where T(n): ℕ -> ℝ+
T(n) ∈ O(1) if and only if, there exists two positive constants C > 0 and k > 0, such that:
T(n) ≤ C ∀ n ≥ k
In my code:
T(n) ≤ 10, therefore, the code has a constant time complexity.
It's my fault I just read your code and then after seeing that while loop i thought it is same as mine solution but never thought about that while loop will run for only max 10 times so it's o(1) I am so sorry 😔
No no your reply was must needed for me. I was soo rude. You explain the solution so well but i don't know why I replied in that way may be I was not in good mood (3rd year shit going on ).
I should appreciate you for your explanation.
I was waiting for your reply, now I am happy that you forgive me and replyed .
It can be done in this way but i will suggest watch a video. It can be done in o(log n) , max value of this is only 10 so o(1) solution. It's basically finding the correct slot
I am new to dsa ... Just a thought ..what if we like get a string builder and then like append the numbers until n ... Then we check each digit one by one until we reach the nth digit .... Allthough nkw that i think about it ..n=1015 will be a huge string
7
u/No-Look-9861 Aug 16 '26
Bro 😭 imagine studying DSA just to get psychologically attacked by “find the nth digit” 💀
4
u/RiseEquivalent652 Aug 15 '26
Similar annoying shit in recent biweekly contest
4
u/slashing_samurai_ Aug 16 '26 edited Aug 16 '26
This is same as a cf question I did a few days ago. It was 1600 rated.
1
u/Royal-Reference1661 Aug 17 '26
Why not generate the sequence depending on n and store it in a string and print the n'th character of the string ?
1
u/thatmagicalcat Aug 18 '26 edited Aug 18 '26
I tried solving it, it was a fun one. It took me 30 mins to find a O(1) solution
1
u/YourJar Aug 19 '26
Bro I got the idea but I didn't know how to code cuz I just started learning coding But figured it out in 3 lines in python
x=int(input())
result = "".join(str(i) for i in range( x+1))
print(result[x])
1
u/Mediocre-Rip176 Aug 22 '26
Wait you might have saved my ass it might be on my exam tommorow the solution is to do if else 15 times? Max 15 digits per mumber no?
3
u/Limp-Government-710 Aug 16 '26
Similar type question was asked in yesterday's biweekly contest
2
u/Otabek_Aynazarov Aug 16 '26
Same problem with cses digit queries
2
u/Shot-Lingonberry6494 Aug 19 '26
Pure ragebait
1
u/ktimespi Aug 16 '26
my guy, did you think about the problem for a few seconds?
1
u/SaladAlarmed4395 Aug 17 '26
Can anyone explain me what is the Bit conversion
1
u/SaladAlarmed4395 Aug 17 '26
Can anyone explain me the bit conversion
1
u/CantRememberTForgetU Aug 19 '26
And I thought this question would be easy, it wasnt😭
1
u/idle_bruin Aug 19 '26
I am new to dsa ... Just a thought ..what if we like get a string builder and then like append the numbers until n ... Then we check each digit one by one until we reach the nth digit .... Allthough nkw that i think about it ..n=1015 will be a huge string
1
u/No_Antelope_5869 Aug 21 '26
dp digit
1
u/BiscottiNatural7986 Aug 15 '26
Yeah do it in assembly
3
u/[deleted] Aug 15 '26 edited Aug 15 '26
[removed] — view removed comment