Let's write all the positive integer numbers one after another from 1 without any…
- User
Let's write all the positive integer numbers one after another from 1 without any delimiters (i.e. as a single string). It will be the infinite sequence starting with 123456789101112131415161718192021222324252627282930313233343536...
Your task is to print the k-th digit of this sequence. Input
The first and only line contains integer k (1 ≤ k ≤ 10^{12}) — the position to process (1-based index).
Output
Print the k-th digit of the resulting infinite sequence.
Examples
Input
7
Output
7
Input
21
Output
5
Assistant
We need to write a program that, given k up to 1e12, returns the k-th digit in the concatenated string of positive integers: "12345678910111213141516...".
We need to find which number the k-th digit belongs to and which digit within that number.
This is a classic problem, often known as "Digits in Sequence" or "Find the nth digit of the infinite integer sequence". The approach: group numbers by their digit length.
Let:
- numbers with 1 digit: 1-9 => 9 numbers, total digits: 9*1 = 9
- numbers with 2 digits: 10-99 => 90 numbers, total digits: 90*2 = 180
- numbers with 3 digits: 100-999 => 900 numbers, total digits: 900*3 = 2700
- ...
- numbers with d digits: count = 9 * 10^{d-1} numbers, total digits = 9 * 10^{d-1} * d
We need to find d such that cumulative digits before that group is < k <= cumulative up to group d.
Let cum[d] = total digits from all numbers with length <= d.
We can compute:
cum[1] = 9 cum[2] = 9 + 180 = 189 cum[3] = 189 + 2700 = 2889 cum[4] = 2889 + 36000 = 38889 cum[5] = 38889 + 450000 = 488889 cum[6] = 488889 + 5400000 = 5888889 cum[7] = 5888889 + 63000000 = 68888889 cum[8] = 68888889 + 720000000 = 788888889 cum[9] = 788888889 + 8100000000 = 8888888889 cum[10] = 8888888889 + 90000000000 = 98888888889 cum[11] = 98888888889 + 990000000000 = 1088888888889? Wait compute: 910^{10}? Actually count for d=11: 910^{10} = 90,000,000,000? Let's recalc: d=11 => numbers from 10^{10} to 10^{11}-1 => count = 9 * 10^{10} (since 10^{11-1} = 10^{10})? Actually standard: for digit length d, numbers start at 10^{d-1} and end at 10^d - 1, inclusive. Count = 9 * 10^{d-1}. So for d=11, count = 9 * 10^{10} = 90,000,000,000? That's 9e10, but note that 10^{10} = 10,000,000,000, times 9 is 90,000,000,000. And total digits = count * d = 90e9 * 11 = 990,000,000,000. So cum[11] would be cum[10] + that. cum[10] = for d=1..10? Let's compute carefully.
We need to compute up to where cum[d] can exceed 1e12. Because k max is 1e12. We need to find d such that cum[d-1] < k <= cum[d].
Alternatively, we can subtract from k the total digits of groups with fewer digits until we find the group.
Algorithm:
- Let d = 1, start = 1, end = 9, count = 9, totalDigits = 9*d
- While k > totalDigits: k -= totalDigits d += 1 start = 10^(d-1) count = 9 * 10^(d-1) totalDigits = count * d
But careful: When d increases, start changes accordingly. Actually we can compute without loops using formulas.
Since k up to 1e12, we can loop over d up to maybe 18? Because numbers with up to 18 digits? Let's estimate: For d=1:9; d=2:180; d=3:2700; d=4:36000; d=5:450000; d=6:5.4e6; d=7:6.3e7; d=8:7.2e8; d=9:8.1e9; d=10:9e10; d=11:9.9e11? Actually compute: d=10: count = 9*10^9 = 9,000,000,000, digits = 9e9 * 10 = 9e10 (90,000,000,000). cum[10] after adding: cum[9] + 90e9. cum[9] we need compute up to d=9: Let's compute cumulative precisely:
We'll compute cum_d = sum_{i=1}^{d} 9 * 10^{i-1} * i.
We can compute values:
d=1: 9 d=2: 9 + 180 = 189 d=3: 189 + 2700 = 2889 d=4: 2889 + 36000 = 38889 d=5: 38889 + 450000 = 488889 d=6: 488889 + 5,400,000 = 5,888,889? Wait 5,400,000? Actually 900,000? Let's recalc: For d=6: count = 9 * 10^{5} = 900,000? Because 10^{5}=100,000, times 9 = 900,000. Then digits = 900,000 * 6 = 5,400,000. So cum[6] = 488,889 + 5,400,000 = 5,888,889. Yes. d=7: count = 910^6 = 9,000,000; digits=9,000,0007=63,000,000; cum[7]=5,888,889+63,000,000=68,888,889. d=8: count=90,000,000? Actually 910^7=90,000,000; digits=90,000,0008=720,000,000; cum[8]=68,888,889+720,000,000=788,888,889. d=9: count=910^8=900,000,000; digits=900,000,0009=8,100,000,000; cum[9]=788,888,889+8,100,000,000=8,888,888,889. d=10: count=910^9=9,000,000,000; digits=9,000,000,00010=90,000,000,000; cum[10]=8,888,888,889+90,000,000,000=98,888,888,889? Actually 8,888,888,889 + 90,000,000,000 = 98,888,888,889. d=11: count=910^10=90,000,000,000; digits=90,000,000,00011=990,000,000,000; cum[11]=98,888,888,889+990,000,000,000=1,088,888,888,889. Now k max = 1e12 = 1,000,000,000,000. So k is less than cum[11] (which is about 1.0889e12). So we only need up to d=10 perhaps, but maybe k can be up to 1e12, which is between cum[10] and cum[11]. Since cum[10] = 98,888,888,889? Wait earlier I computed cum[10] as 98,888,888,889? That's about 9.888e10, which is 98.9 billion, far less than 1e12. Actually check: cum[10] I just computed as 98,888,888,889? That seems too small: 98.9 billion, but 1e12 is 1000 billion. Actually something off: Let's compute carefully:
We need to ensure numbers: For d=1: 9 d=2: 910^1 = 90? Wait count for d-digit numbers: from 10^{d-1} to 10^d -1 inclusive => number of numbers = 10^d - 10^{d-1} = 9 * 10^{d-1}. So for d=2: count = 9 * 10^{1} = 90 (numbers 10-99). Yes, earlier I mistakenly used 90? I used 90 for d=2? I used 180 digits total, which is 902 = 180, correct. Good. d=3: count = 9 * 10^{2} = 900, digits = 9003 = 2700, correct. d=4: count = 910^3 = 9000? Actually 10^{3}=1000, times 9 = 9,000. digits = 9,0004 = 36,000. I earlier wrote 36,000, correct. d=5: count=910^4=90,000; digits=90,0005=450,000, correct. d=6: count=910^5=900,000; digits=900,0006=5,400,000, correct. d=7: count=910^6=9,000,000; digits=9,000,0007=63,000,000, correct. d=8: count=910^7=90,000,000; digits=90,000,0008=720,000,000, correct. d=9: count=910^8=900,000,000; digits=900,000,0009=8,100,000,000, correct. d=10: count=910^9=9,000,000,000; digits=9,000,000,00010=90,000,000,000, correct. d=11: count=910^10=90,000,000,000; digits=90,000,000,00011=990,000,000,000, correct. d=12: count=910^11=900,000,000,000; digits=900,000,000,000*12=10,800,000,000,000, which exceeds 1e12 by far.
Now compute cumulative:
cum[1] = 9 cum[2] = 9 + 180 = 189 cum[3] = 189 + 2700 = 2889 cum[4] = 2889 + 36000 = 38889 cum[5] = 38889 + 450000 = 488889 cum[6] = 488889 + 5,400,000 = 5,888,889 cum[7] = 5,888,889 + 63,000,000 = 68,888,889 cum[8] = 68,888,889 + 720,000,000 = 788,888,889 cum[9] = 788,888,889 + 8,100,000,000 = 8,888,888,889 cum[10] = 8,888,888,889 + 90,000,000,000 = 98,888,888,889 cum[11] = 98,888,888,889 + 990,000,000,000 = 1,088,888,888,889
Yes. So cum[10] is about 9.8889e10? Actually 98,888,888,889 is roughly 9.889e10 (98.9 billion). That's less than 1e12? Actually 1e12 = 1,000,000,000,000 (1000 billion). So cum[10] is 98.9 billion, which is two orders of magnitude smaller. So k up to 1e12 is much larger than cum[10]; it falls into d=11 group for k up to 1e12, because cum[11] = 1,088,888,888,889 which is > 1e12. So k max 1e12 is less than cum[11]? Wait cum[11] is about 1.0889e12. Since k max is 1e12, which is less than 1.0889e12, so indeed k can be in d=11 as well. But note: cum[10] = 98,888,888,889, which is about 9.89e10, and cum[11] is about 1.089e12. So for k between 1 and 9.888e10, it's in d <=10; for k > 9.888e10 up to 1.089e12, it's in d=11. Since max k=1e12, k can be in d=11. So we need to handle d up to at least 11. But maybe also d=12? For k=1e12, it's less than cum[11]? Check: cum[11] = 1,088,888,888,889 > 1,000,000,000,000, so k=1e12 is < cum[11], so it's in d=11. So max d needed is 11. But to be safe, we can loop.
Thus algorithm:
- Initialize d = 1.
- While k > 9 * (10**(d-1)) * d: // i.e., total digits in group d k -= totalDigits d += 1
- After this, k is the position within the group of d-digit numbers.
- The group starts at number start = 10^{d-1}.
- We need to find which number in this group corresponds to the k-th digit. Since each number in this group has d digits, the offset within the group in terms of numbers is: offset = (k - 1) // d. So the actual number is: num = start + offset.
- Then digit index within that number: pos = (k - 1) % d. (0-based from leftmost? Typically we want the digit at that position. But careful: The string is concatenated without separators, so digits are counted from leftmost digit of each number. So if we have number num, its decimal representation as a string of length d, and we want the character at position pos (0-indexed from left). So we can get that digit by converting num to string and indexing pos.
- Then output that digit.
But note: k is up to 1e12, so d up to 11, start up to 10^{10} (which is 10,000,000,000) and offset may be up to (count-1) i.e., about 90e9, so num can be as large as about 100,000,000,000 (i.e., 10^11 - 1). That's within 64-bit integer range (max 9e18). So we can use 64-bit (long long in C++, int64 in Python no problem). In Python integers are arbitrary precision anyway.
So we can implement this directly.
We must ensure the loop condition uses large numbers; Python can handle.
Alternatively, we can compute d by using formula: find smallest d such that k <= cum[d]. We can precompute cum for d=1..some.
But simple loop is fine as d max is maybe 12, so just loop.
Edge Cases: k small. Example: k=7 -> d=1? Check: totalDigits for d=1 = 9. k=7 <=9 so remains d=1. Then start=1, offset=(7-1)//1=6, num=1+6=7, pos=0, digit 7. Good.
k=21: cum[1]=9, cum[2]=189. So k>9, subtract 9 => k=12 in d=2 group. start=10, offset=(12-1)//2 = 11//2=5, num=10+5=15, pos=(12-1)%2=1 => index 1 (0-based) in "15": digits: '1','5', so position 1 -> '5'. Output 5. Good.
Now for large k, works.
But careful: when d=1, start = 10^{0}=1, count=9, offset maximum is 8.
Implementation:
- Read k as integer.
- d = 1
- while True: total = 9 * (10**(d-1)) * d if k <= total: break k -= total d += 1
- Then compute offset = (k-1)//d, digit_index = (k-1)%d.
- num = 10**(d-1) + offset.
- Convert num to string, digit = str(num)[digit_index]
- Print digit.
We need to be careful with exponentiation: 10**(d-1) might be huge but okay. However for d=1, 10**(0)=1, total=911=9.
That's correct.
Now consider k exactly at boundary between groups: Example k=9: d=1, total=9, k<=9 -> stays. offset=(9-1)//1=8, num=1+8=9, pos=0, digit '9'. Good. Next k=10: Should fall into d=2. Let's test: d=1 total=9, k=10 >9 => k=10-9=1, d=2. Now total for d=2=180, k=1 <=180. offset=(1-1)//2=0, num=10+0=10, pos=0 -> '1'. So 10th digit is '1'? Let's check string: "12345678910111213...": positions: 1:'1',2:'2',3:'3',4:'4',5:'5',6:'6',7:'7',8:'8',9:'9',10:'1',11:'0',12:'1',13:'1',... Yes position 10 is '1' of 10. Good.
Now test k=189? cum[2]=189. k=189: For d=1, total=9, k>9 => k=180, d=2. total=180, k=180 <=180, so stays d=2. offset=(180-1)//2=179//2=89? Actually integer division: 179//2=89 (since 2*89=178). So offset=89, num=10+89=99, pos=(180-1)%2=179%2=1. So number 99, digits: '9','9', index 1 -> '9'. So 189th digit is '9'? Let's check: The last digit of 99 should be position? We need to compute manually: After 98, we have 99. Let's calculate total digits up to 99: numbers 1-9:9 digits; 10-99: 90 numbers *2 =180 digits, total 189 digits. So the last digit of 99 is the 189th digit. Yes it's '9'. So correct.
Now k=190: should be first digit of 100. d=2? At k=190>180? Actually after subtract d=1, k=181, compare with d=2 total=180? Wait steps: d=1 total=9, k=190>9 => k=181, d=2. For d=2, total=180, but k=181 >180, so we subtract 180 => k=1, d=3. total for d=3=2700, k=1 <=2700. Then start=100, offset=0, num=100, pos=0 -> '1'. So 190th digit is '1' of 100. Good.
Thus algorithm works.
Now we must implement with Python (since code output likely needed). The input is a single integer k. Print the digit.
But the problem statement: "Let's write all the positive integer numbers one after another from 1 without any delimiters (i.e. as a single string). It will be the infinite sequence starting with 123456789101112131415161718192021222324252627282930313233343536...
Your task is to print the k-th digit of this sequence. Input
The first and only line contains integer k (1 ≤ k ≤ 10^{12}) — the position to process (1-based index).
Output
Print the k-th digit of the resulting infinite sequence.
Examples
Input
7
Output
7
Input
21
Output
5"
So we need to produce code.
We need to handle k up to 1e12, but Python int fine.
Implementation steps:
def solve(): import sys k = int(sys.stdin.readline().strip()) d = 1 while True: first = 10**(d-1) count = 9 * first total = count * d if k <= total: break k -= total d += 1 # now k is 1-indexed within the group offset = (k - 1) // d pos = (k - 1) % d num = 10**(d-1) + offset # get digit digit_str = str(num)[pos] print(digit_str)
That's it.
Edge Cases: For d=1, first=1, count=9, total=9.
Now we might also want to handle potential overflow of exponentiation, but Python fine.
Complexities: O(d) where d <= 12, trivial.
Let's test with given examples:
Example 1: k=7 -> d=1, total=9, k<=9; offset=(6)//1=6; num=1+6=7; pos=0; str(7)[0]='7' -> prints 7.
Example 2: k=21 -> d=1 total=9, k=21>9 -> k=12, d=2; total=180, k<=180; offset= (12-1)//2 =11//2=5; num=10+5=15; pos=11%2=1; str(15)[1]='5' -> prints 5.
Now test some random values to ensure.
We'll test k=1 => d=1, offset=0,num=1,pos=0 => '1'.
k=9 => '9'.
k=10 => '1'.
k=11 => '0'.
k=12 => '1'.
k=13 => '1'.
k=14 => '1'.
k=15 => '2'? Actually positions: let's list: "12345678910111213..." So pos1:1,2:2,3:3,4:4,5:5,6:6,7:7,8:8,9:9,10:1,11:0,12:1,13:1,14:1,15:2? Wait careful: After 10 (digits 1,0) we have 11 (1,1), 12 (1,2). So positions:
1:1 2:2 3:3 4:4 5:5 6:6 7:7 8:8 9:9 10:1 (of 10) 11:0 (of 10) 12:1 (of 11) 13:1 (of 11) 14:1 (of 12?) Actually 12: digits: 1 and 2, so position 13 is 1? Let's list properly:
Concatenation: 1,2,3,4,5,6,7,8,9,1,0,1,1,1,2,1,3,1,4,1,5,1,6,... So: Index: 1:1 2:2 3:3 4:4 5:5 6:6 7:7 8:8 9:9 10:1 (from 10) 11:0 12:1 (from 11) 13:1? Actually 11 is "1" then "1". So after "10" we have "11": first digit of 11 is at index 12, second digit at index 13. So index 12:1, index13:1. Then "12": index14:1, index15:2. So indeed index15 is 2. So k=15 => output 2.
Now test our code: k=15 => after subtract d=1 (9) => k=6? Wait recalc: k=15 >9 => k=6, d=2. total for d=2=180, k=6 <=180. offset=(6-1)//2 =5//2=2, num=10+2=12, pos=(6-1)%2=5%2=1 => str(12)[1] = '2'. Good.
Now test k=188? That is near end of two-digit numbers. k=188 => subtract d=1: k=179, d=2, total=180, k=179 <=180. offset=(179-1)//2=178//2=89, num=10+89=99, pos=(179-1)%2? Actually (k-1)=178, 178%2=0 => pos=0 => str(99)[0]='9'. So 188th digit is first digit of 99? But we thought earlier the digits: 99 is two digits, first digit at position? Let's compute: numbers 10-98: 89 numbers? Actually numbers from 10 to 98 inclusive are 89? 10 to 98: that's 98-10+1 = 89 numbers. Each 2 digits => 178 digits. Then digits from 1-9:9 digits, total before 99: 9+178=187. So first digit of 99 is at position 188, second digit at 189. So yes, k=188 gives '9' (first digit). Good.
Now test k=1000000000000 (1e12). Let's simulate to see if our code handles large numbers correctly.
Compute d: We need to find which group. cum[10] = 98,888,888,889; cum[11] = 1,088,888,888,889. Since 1e12 = 1,000,000,000,000 > cum[10] and < cum[11], so d=11. So after subtracting d=1..10 digits, we get k' = 1e12 - cum[10] = 1,000,000,000,000 - 98,888,888,889 = 901,111,111,111? Actually compute: 1,000,000,000,000 - 98,888,888,889 = 901,111,111,111. Yes. Then total for d=11 group = 990,000,000,000. So k'=901,111,111,111 is within that. Then offset = (k'-1)//11, num = 10**10 + offset (since start = 10^(11-1) = 10^10 = 10,000,000,000). offset = (901,111,111,111 - 1) // 11 = 901,111,111,110 // 11. 11 * 81,919,191,010 =? Actually 11 * 81,919,191,010 = 901,111,101,110? Not exactly. Let's compute properly: 901,111,111,110 / 11. 1181,919,191,010 = 901,111,101,110? Wait 81,919,191,010 * 11 = 81,919,191,01010 + 81,919,191,010 = 819,191,910,100 + 81,919,191,010 = 901,111,101,110. That's 10,000 less? Actually 901,111,111,110 - 901,111,101,110 = 10,000. So it's not exact. We'll compute: 901,111,111,110 / 11 = 81,919,191,010.0? Actually 11*81,919,191,010 = 901,111,101,110; so the remainder is 10,000. So offset would be floor division: (901,111,111,110) // 11 = 81,919,191,010? Let's do precise: 11 * 81,919,191,010 = 901,111,101,110. That leaves remainder 10,000? 901,111,111,110 - 901,111,101,110 = 10,000, which is less than 11? Actually 10,000 < 11? No, 10,000 > 11. So my multiplication must be off. Wait re-evaluate: 81,919,191,010 * 11:
81,919,191,010 * 10 = 819,191,910,100. 81,919,191,010 * 1 = 81,919,191,010. Sum = 901,111,101,110. Yes.
But our numerator is 901,111,111,110, difference = 10,000. So 81,919,191,01011 is less than numerator by 10,000. So numerator / 11 = 81,919,191,010 + (10,000/11) ≈ 81,919,191,010 + 909.09. So floor division = 81,919,191,010? Actually floor division yields integer part, which is 81,919,191,010 if the remainder is 10,000? Wait 10,000/11 = 909.09, so 81,919,191,010 + 909 = 81,919,191,919? No, because 81,919,191,010 * 11 = 901,111,101,110. If we add 909 to the quotient, 90911 = 9,999, total becomes 901,111,101,110 + 9,999 = 901,111,111,109. Still 1 short of 901,111,111,110. Then add 1: (909+1)=910, 91011=10,010? Actually 91011 = 10,010, which overshoots? Let's do systematic: We need to find q = floor((901,111,111,110)/11). Divide: 11 * 81,919,191,010 = 901,111,101,110, remainder = 10,000. Since remainder > 11, we can increase q further. Actually remainder must be less than divisor; if remainder >= 11, that means we underestimated q. So we need to add floor(remainder/11) to q. 10,000 // 11 = 909 (since 11909=9,999), remainder becomes 1. So q = 81,919,191,010 + 909 = 81,919,191,919, and remainder = 1. Check: 81,919,191,919 * 11 =? Compute: 81,919,191,91910 = 819,191,919,190; +81,919,191,919 = 901,111,111,109. That's one less than 901,111,111,110. So remainder = 1. That matches. So offset = 81,919,191,919. Then num = 10,000,000,000 + 81,919,191,919 = 91,919,191,919? Actually 10^10 = 10,000,000,000. Sum = 91,919,191,919. Then pos = remainder = 1? Actually (k-1) % d = (901,111,111,111 -1) % 11 = 901,111,111,110 % 11. We computed remainder = 1. So pos = 1 (0-indexed). So digit = str(91919191919?) Actually num=91,919,191,919. Its string representation: "91919191919"? Let's see: 91,919,191,919 is 11 digits? Actually 10^10 = 10,000,000,000 (11 digits? Wait 10^10 = 10,000,000,000 which is 11 digits? 10,000,000,000 has 11 digits? Actually 10^10 = 10,000,000,000 is 11 digits because 10^0=1 (1 digit), 10^1=10 (2 digits), ... 10^n has n+1 digits. For d=11, numbers are from 10^10 to 10^11-1 inclusive, so they are 11-digit numbers. 10^10 = 10,000,000,000 indeed has 11 digits. So num = 10,000,000,000 + offset = 10,000,000,000 + 81,919,191,919 = 91,919,191,919 which is 11 digits: 9 1 9 1 9 1 9 1 9 1 9? Let's count: 91,919,191,919: grouping: 91,919,191,919 -> digits: 9,1,9,1,9,1,9,1,9,1,9? Actually that would be 11 digits: 9 (billions?), write it: 91,919,191,919 = 91 919 191 919. Actually 91,919,191,919 in full: 91,919,191,919. So digits: 9,1,9,1,9,1,9,1,9,1,9? That seems alternating 9 and 1. Let's check: 91,919,191,919 = 91 919 191 919. So groups: 91 (two digits: 9,1), 919 (9,1,9), 191 (1,9,1), 919 (9,1,9). Concatenated: 9,1,9,1,9,1,9,1,9,1,9? Actually join: from 91: 9,1; then 919: 9,1,9 gives sequence so far: 9,1,9,1,9; then 191: 1,9,1 gives: 9,1,9,1,9,1,9,1? Let's do systematically: Write number as digits from left:
- Ten billions place: 9? Actually 91,919,191,919 is 11 digits. The highest place is hundred billions? Actually 10^10 is ten billions (10,000,000,000) which is 11 digits: positions: hundred billions, ten billions, billions, ... Let's break:
10^10 = 10,000,000,000 (11 digits: 1 followed by 10 zeros). So the place values for 11-digit numbers: hundred billions (10^10), ten billions (10^9), billions (10^8), hundred millions (10^7), ten millions (10^6), millions (10^5), hundred thousands (10^4), ten thousands (10^3), thousands (10^2), hundreds (10^1), tens/units (10^0). But easier: just string.
91,919,191,919 as string: "91919191919"? Actually 91,919,191,919 -> write without commas: 91919191919? Wait 91,919,191,919 is 11 digits? Let's count: 91,919,191,919 -> digits: 9,1,9,1,9,1,9,1,9,1,9? That would be 11 digits: positions: 9 (10^10), 1 (10^9), 9 (10^8), 1 (10^7), 9 (10^6), 1 (10^5), 9 (10^4), 1 (10^3), 9 (10^2), 1 (10^1), 9 (10^0). That yields number 910^10 + 110^9 + 910^8 + 110^7 + 910^6 + 110^5 + 910^4 + 110^3 + 910^2 + 110^1 + 9 = 910^10 = 90,000,000,000; +110^9=1,000,000,000 => 91,000,000,000; +910^8=900,000,000 => 91,900,000,000; +110^7=10,000,000 => 91,910,000,000; +910^6=9,000,000 => 91,919,000,000; +110^5=100,000 => 91,919,100,000; +910^4=90,000 => 91,919,190,000; +110^3=1,000 => 91,919,191,000; +910^2=900 => 91,919,191,900; +110=10 => 91,919,191,910; +9=9 => 91,919,191,919. Yes matches. So string is "91919191919"? Actually it would be "91919191919"? The digits we listed: 9,1,9,1,9,1,9,1,9,1,9. That string would be "91919191919". But that's only 11 digits? "91919191919" has length? Count: 9 1 9 1 9 1 9 1 9 1 9 = 11 characters. So indeed "91919191919". So the digit at pos 1 (0-index) is the second digit: which is '1'. So output would be '1'. So for k=1e12, answer should be '1'. That seems plausible but not necessary to verify.
Our code will compute correctly.
Now we need to produce final answer: the code itself.
But maybe we should note that input may contain leading/trailing spaces, but using strip is fine.
Let's produce the Python code.
We can also speed up by using math.log10? But not needed.
One nuance: while loop uses 10**(d-1) each time; that's fine. But we could precompute powers but it's okay.
We also need to be careful about integer division with negative numbers, but not relevant.
Now test with some other values: For k = 100, let's compute manually:
k=100: subtract d=1: 100-9=91, d=2, total=180, k=91 <=180. offset=(91-1)//2=90//2=45, num=10+45=55, pos=(91-1)%2=90%2=0 => digit str(55)[0] = '5'. So output '5'. Let's verify with actual string: digits: positions 1-9: 1-9, 10:1,11:0,12:1,13:1,14:1,15:2,16:1,17:3, ... up to position 100? We can compute: two-digit numbers from 10 to 55. Numbers from 10 to 55 inclusive: count = 46 numbers (10..55 inclusive). Each 2 digits => 92 digits. Plus first 9 digits => total 101 digits for numbers up to 55? Actually numbers 10-55 give 46 numbers => 92 digits. Add 9 from 1-9 => 101 digits for digits up to the end of 55. That means the last digit of 55 is at position 101. But we got position 100 is the first digit of 55? Our calculation gave num=55, pos=0 -> first digit of 55. But total digits up to end of 54: numbers 1-9 (9) + numbers 10-54 (45 numbers => 90 digits) = 99 digits. So position 100 is the first digit of 55, which is '5'. So correct.
Now test with k=101: our code would give offset = (101-1-9? Actually after subtract d=1: 101-9=92, d=2. Then offset=(92-1)//2=91//2=45, num=10+45=55, pos=(92-1)%2=91%2=1 => second digit of 55: '5'? Actually second digit of 55 is '5'. So position 101 is '5'. Indeed total digits up to end of 55: 9+92=101, so last digit of 55 is position 101. So correct.
All good.
Now implement.
Potential pitfalls: For d=1, we used total = 9 * (10**(d-1)) * d = 911=9, good.
But note: The numbers start from 1, not 0. So group definitions correct.
Now about input reading: The example input has blank line? In problem statement they show "Input" then blank then "7"? Actually format: It says "Input" then a blank line, then "7"? Usually they mean the input is just the number. So we can read line.
Now final code:
import sys
def main(): k = int(sys.stdin.readline()) d = 1 while True: cnt = 9 * (10**(d-1)) total = cnt * d if k <= total: break k -= total d += 1 # k now 1-indexed within d-digit numbers offset = (k - 1) // d pos = (k - 1) % d num = 10**(d-1) + offset ans = str(num)[pos] print(ans)
if name == "main": main()
That solves.
But we can optimize by using while loop with condition, but it's fine.
Edge Cases: Suppose k is exactly equal to total for d group and we break? In our loop, we break if k <= total. That means if k == total, we stay in this group. That's correct because the total digits for that group includes up to the last digit of the last number in that group. So we want to map to that last number. So offset calculation works: (total - 1)//d = (countd -1)//d = count - 1 if total% d == 0? Actually total = count * d. Then (total-1)//d = (countd -1)//d = count - 1 if d>1? Because countd -1 divided by d gives count - 1/d, floor => count-1. So offset = count-1, num = start + count-1 = last number, pos = (total-1)%d = (countd -1) % d = d-1 (since (count*d -1) mod d = (0 -1) mod d = d-1). So we get the last digit of the last number. That's correct.
Now ensure Python code uses integer arithmetic.
Now test with large d: d=11, 10**(10) is 10000000000, which is okay.
Now final code print.
But sometimes people use sys.stdin.read().strip() to handle empty lines, but fine.
Thus answer is the code.
I'll now produce final answer as the Python code. ```python
import sys
def main() -> None: k = int(sys.stdin.readline())
d = 1 # current digit length while True: # number of d-digit numbers and total digits contributed by them count = 9 * (10 ** (d - 1)) total = count * d if k <= total: break k -= total d += 1 # k is now the 1‑based index inside the block of d‑digit numbers offset = (k - 1) // d # how many numbers we skip pos = (k - 1) % d # which digit inside the chosen number (0‑based) number = 10 ** (d - 1) + offset answer = str(number)[pos] print(answer)if name == "main": main()