medium
0 views

Infinite Sequence Nth Digit

Find the Nth digit in the infinite sequence formed by concatenating positive integers starting from 1.

Understand the Problem

Problem Statement

Given a positive integer N, find and print the Nth digit in the infinite sequence formed by concatenating all positive integers: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ... and so on.

For example, the sequence begins as: 1234567891011121314151617181920212223...

The 5th digit is 5, and the 11th digit is 0 (from the number 10).

Constraints

  • 1 ≤ N ≤ 10^9
  • N is a positive integer
  • The sequence starts from 1 and goes to infinity

Examples

Example 1
Input
5
Output
5
Explanation

The infinite sequence starts as 123456789101112... The 5th digit is 5, which comes from the single digit number 5.

Example 2
Input
11
Output
0
Explanation

The sequence is 123456789101112... The first 9 digits are from numbers 1-9. The 10th and 11th digits come from the number 10. Specifically, the 10th digit is 1 and the 11th digit is 0.

Example 3
Input
15
Output
2
Explanation

The sequence is 123456789101112131415... The 15th digit is 2, which comes from the number 12 (specifically the second digit of 12).

Solution

#include <stdio.h>
#include <math.h>

int findNthDigit(int n) {
    long long digits = 1;
    long long count = 9;
    long long start = 1;
    
    // Find the digit group (1-digit, 2-digit, etc.)
    while (n > digits * count) {
        n -= digits * count;
        digits++;
        count *= 10;
        start *= 10;
    }
    
    // Find the specific number
    start += (n - 1) / digits;
    
    // Find the specific digit in that number
    char numberStr[20];
    sprintf(numberStr, "%lld", start);
    
    return numberStr[(n - 1) % digits] - '0';
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", findNthDigit(n));
    return 0;
}
Time:O(log N) - The algorithm iterates through digit groups (1-digit, 2-digit, etc.) which takes logarithmic time relative to N.
Space:O(1) - Uses only a constant amount of extra space regardless of input size.
Approach:

The C solution implements the mathematical approach:

  1. Initialize variables to track digit length (digits), count of numbers in current group (count), and starting number of current group (start).
  2. Loop to find which digit group contains position N by subtracting the total digits from previous groups.
  3. Calculate the specific number that contains the Nth digit using integer division.
  4. Convert the number to string and extract the specific digit using modulo arithmetic.
  5. Return the digit as an integer by subtracting ASCII '0'.

Visual Explanation

Loading diagram...
All Problems