This needs cleaning up, but solves OP's problem fairly quickly:
fn get_digit(k: u64) -> u64 {
if k < 10 { return k; }
let mut p: u64 = 2; // Current power of 10
let mut r: u64 = k-9; // Remaining indices
loop {
// Iterate with d = 180, 2700, 81000...
let d = 10_u64.pow((p-1) as u32) * p * 9;
if r <= d {
let i = (r-1) / p; // Index among p-digit numbers. Is 0-indexed, so i=0 would be 10, 100, 1000...
let b = (r-1) % p; // The digit to use from n, in big endian, so b=0 would be "1" from 10.
let l = p - b - 1; // b, converted to "little endian". So l=0 would be the "2" from 12.
let n = 10_u64.pow((p-1) as u32) + i; // The number we take a digit from
return (n / (10_u64.pow(l as u32))) % 10;
}
r -= d;
p += 1;
}
}
fn main() {
println!("Input: 20, Output: {}", get_digit(20));
println!("Input: 123, Output: {}", get_digit(123));
println!("Input: 5318008, Output: {}", get_digit(5318008));
println!("Input: 1000000000000000000, Output: {}", get_digit(1000000000000000000));
println!("Input: 560981764105518902, Output: {}", get_digit(560981764105518902));
}
It's basically O(log(k)) time.
