Nth Digit - Practice Coding Problems

Nth Digit - Problem

Given an integer n, return the nth digit of the infinite integer sequence [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...].

The sequence is formed by concatenating all positive integers: 123456789101112131415...

Note: The digit indexing starts from 1 (1-indexed).

Input & Output

Example 1 — Finding 11th Digit

$ Input: n = 11

› Output: 0

💡 Note: Sequence: 123456789101112... The 11th digit is the second digit of 10, which is 0

Example 2 — Single Digit

$ Input: n = 3

› Output: 3

💡 Note: Sequence: 123456789... The 3rd digit is simply 3

Example 3 — Two-Digit Range

$ Input: n = 15

› Output: 2

💡 Note: Sequence: 123456789101112131415... Position 15 is the first digit of 12, which is 1. Wait, let me recalculate: positions 1-9 are digits 1-9, positions 10-11 are '1','0' from 10, positions 12-13 are '1','1' from 11, positions 14-15 are '1','2' from 12. So 15th digit is '2'

Constraints

1 ≤ n ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input

Given n = 11

Sequence

Concatenate integers: 123456789101112...

Output

Find 11th digit which is 0

Key Takeaway

🎯 Key Insight: Use mathematical patterns of digit contributions to avoid counting one by one

Asked in

G Google 12 Apple 8 MS Microsoft 6

The key insight is recognizing the mathematical pattern: 1-digit numbers contribute 9 digits, 2-digit numbers contribute 180 digits, etc. Best approach uses direct mathematical calculation to find the target number and digit position. Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Counting	O(n)	O(1)	Count digits one by one from 1 until reaching the nth position
Binary Search on Answer Space	O(log² n)	O(1)	Binary search to find the number that contains the nth digit
Mathematical Pattern Recognition	O(log n)	O(1)	Use mathematical patterns to directly calculate which number contains the nth digit

Brute Force Counting — Algorithm Steps

Start from number 1
For each number, count its digits
Keep track of total digits seen
When total >= n, find the specific digit in current number

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Counting

Begin with number 1, count its digits

Continue

Move to next numbers, accumulate digit count

Find Position

When count >= n, locate exact digit in current number

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int countDigits(int num) {
    if (num == 0) return 1;
    int count = 0;
    while (num > 0) {
        count++;
        num /= 10;
    }
    return count;
}

int solution(int n) {
    int count = 0;
    int num = 1;
    
    while (1) {
        int digits = countDigits(num);
        if (count + digits >= n) {
            char numStr[20];
            sprintf(numStr, "%d", num);
            int pos = n - count - 1;
            return numStr[pos] - '0';
        }
        count += digits;
        num++;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

In worst case, we iterate through approximately n digits

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

78.0K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler