Here is the link to the contest. All problems are from Codeforces' problemset.
A. Nth Digit in Sequence
Solution
The problem requires us to find the n-th
digit in an infinite sequence formed by concatenating all positive integers starting from 1.
Observations:
- The sequence starts as:
123456789101112131415...
, and we need to determine the digit at position (n). A simple way to construct the sequence is to append numbers as strings until we reach the required length.
Approach:
- Initialize an empty string
sequence
. - Iterate from
1
onwards, converting each number to a string and appending it tosequence
. - Stop when
sequence
reaches at leastn
characters. Print the
n-th
digit (adjusting for 0-based indexing).Complexity Analysis:
Since numbers grow in length, the loop runs approximatelyO(sqrt{n})
times, making the approach efficient.
Code
n = int(input())
sequence = ""
for num in range(1, 1000):
sequence += str(num)
if len(sequence) >= n: # You can stop early when sequence is long enough
break
print(sequence[n - 1])