Nth Character in Concatenated Decimal String

Problem Statement

Consider the infinite string formed by concatenating all positive integers:

123456789101112131415161718192021222324...

Given an integer n, find the nth character of this string using 1-based indexing.

Example 1

Input: n = 10
Output: '1'

The string starts as:

1234567891...
         ^
         10th character

Therefore, the answer is '1'.

Example 2

Input: n = 11
Output: '0'

The string starts as:

12345678910...
          ^
          11th character

Therefore, the answer is '0'.

1. Understanding the Pattern

The important observation is that numbers can be grouped according to their number of digits.

1-digit numbers

Numbers from 1 to 9:

1 2 3 4 5 6 7 8 9

There are:

9 numbers

Each has 1 digit.

So total characters:

9 × 1 = 9

2-digit numbers

Numbers from 10 to 99.

There are:

99 - 10 + 1 = 90 numbers

Each number has 2 digits.

Therefore:

90 × 2 = 180 characters

3-digit numbers

Numbers from 100 to 999.

There are:

900 numbers

Each has 3 digits.

Therefore:

900 × 3 = 2700 characters

The pattern becomes:

So instead of generating the infinite string, we can skip entire groups of numbers.

2. Main Idea

Suppose:

n = 100

We know that the first 9 characters belong to:

1 to 9

So remove those characters:

100 - 9 = 91

Now we know the answer belongs to the 2-digit number range.

The 2-digit range contains:

90 × 2 = 180 characters

Since 91 <= 180, the required character is somewhere between 10 and 99.

Now we need to determine:

1. Which number contains the character?

2. Which digit inside that number is the answer?

3. Finding the Correct Number

Suppose we are inside a range where every number has digits digits.

For example:

10, 11, 12, 13, 14, ...

Each number has 2 digits.

If the remaining position is N, then the number containing that position is:

start + (N - 1) / digits

Why do we use N - 1?

Because our position is 1-based, while integer division works naturally with a 0-based offset.

For example:

N = 1
digits = 2
start = 10

Then:

number = 10 + (1 - 1) / 2
       = 10

For:

N = 2

we still get:

number = 10 + (2 - 1) / 2
       = 10

For:

N = 3

we get:

number = 10 + (3 - 1) / 2
       = 11

So positions map like this:

Position     Number
   1           10
   2           10
   3           11
   4           11
   5           12
   6           12

4. Finding the Digit Inside the Number

Once we find the number, we need to find which digit of that number is required.

The formula is:

index = (N - 1) % digits

Again, we subtract 1 because Java strings use 0-based indexing.

For example:

N = 3
digits = 2

Then:

index = (3 - 1) % 2
      = 0

The number is:

11

Index 0 gives:

'1'

5. Java Implementation

class Solution {
    public char nthCharacter(int n) {

        long N = n;
        long digits = 1;
        long count = 9;
        long start = 1;

        // Find the range containing the nth character
        while (N > digits * count) {
            N -= digits * count;

            digits++;
            count *= 10;
            start *= 10;
        }

        // Find the number containing the character
        long number = start + (N - 1) / digits;

        // Find the digit inside that number
        int index = (int) ((N - 1) % digits);

        String str = String.valueOf(number);

        return str.charAt(index);
    }
}

6. Code Explanation

Step 1: Initialize Variables

long N = n;
long digits = 1;
long count = 9;
long start = 1;

Here:

N

Stores the remaining position.

long N = n;

We use long so arithmetic operations are safe.

digits

Represents the number of digits in the current range.

Initially:

digits = 1

because we start with numbers 1–9.

count

Represents how many numbers are in the current range.

Initially:

count = 9

because there are 9 one-digit numbers.

start

Represents the first number of the current range.

Initially:

start = 1

7. Skipping Complete Ranges

while (N > digits * count) {
    N -= digits * count;

    digits++;
    count *= 10;
    start *= 10;
}

This is the most important part of the solution.

The expression:

digits * count

gives the total number of characters in the current range.

For example:

digits = 1
count = 9

total = 1 × 9
      = 9

If N is greater than 9, the answer cannot be in the first range.

Therefore, we skip those 9 characters:

N -= 9;

Then move to the next range:

digits = 2
count = 90
start = 10

8. Why count *= 10?

Consider the ranges:

1 – 9        → 9 numbers
10 – 99      → 90 numbers
100 – 999    → 900 numbers
1000 – 9999  → 9000 numbers

Every time we increase the number of digits, the number of values becomes 10 times larger.

Therefore:

count *= 10;

9. Why start *= 10?

The starting numbers are:

1
10
100
1000
10000

Each new range starts with one additional zero.

Therefore:

start *= 10;

10. Finding the Actual Number

After the loop finishes:

long number = start + (N - 1) / digits;

At this point, we know that the answer belongs to the current digit range.

For example:

N = 5
digits = 2
start = 10

Then:

number = 10 + (5 - 1) / 2
       = 10 + 4 / 2
       = 12

So the fifth character in this range belongs to number 12.

11. Finding the Character Position

Now calculate:

int index = (int) ((N - 1) % digits);

Suppose:

N = 5
digits = 2

Then:

index = (5 - 1) % 2
      = 0

The number is:

12

Java uses zero-based indexing:

Index:  0  1
        ↓  ↓
Number: 1  2

Therefore:

str.charAt(0)

returns:

'1'

12. Complete Dry Run

Let's take:

n = 11

The string starts:

123456789101112...

Initial values

N = 11
digits = 1
count = 9
start = 1

The current range contains:

1 × 9 = 9 characters

Since:

11 > 9

skip the first range:

N = 11 - 9
  = 2

Move to the next range:

digits = 2
count = 90
start = 10

Now:

N = 2

and:

2 <= 2 × 90

So the answer is in the 10–99 range.

Find the number

number = start + (N - 1) / digits

       = 10 + (2 - 1) / 2

       = 10

Find the index

index = (N - 1) % digits

      = (2 - 1) % 2

      = 1

Convert number to string:

"10"

Character at index 1:

'0'

Therefore:

Output: '0'

13. Another Dry Run: n = 10

The string is:

12345678910...

Initial:

N = 10

Skip:

1–9 → 9 characters

So:

N = 10 - 9
  = 1

Now:

digits = 2
start = 10

Find number:

number = 10 + (1 - 1) / 2
       = 10

Find index:

index = (1 - 1) % 2
      = 0

Therefore:

"10".charAt(0)

is:

'1'

Answer:

'1'

14. Why Not Generate the String?

A simple approach might be:

StringBuilder sb = new StringBuilder();

for (int i = 1; ; i++) {
    sb.append(i);
}

Then we could return:

sb.charAt(n - 1);

But this is not efficient.

For:

n = 1,000,000,000

we would need to generate an enormous amount of data.

This would require:

• Large memory

• Large execution time

• Unnecessary string construction

Instead, our solution skips entire groups of numbers.

15. Complexity Analysis

There are only a few digit ranges to process.

For example:

1 digit
2 digits
3 digits
...
9 digits
10 digits

Therefore, the loop runs approximately O(log n) times.

Time Complexity

O(log n)

Auxiliary Space

O(1)

The solution does not create the entire concatenated string.

16. Important Formula Summary

The entire solution can be remembered using these three formulas.

Total characters in a range

digits × count

Number containing the answer

start + (N - 1) / digits

Index inside the number

(N - 1) % digits

These three calculations solve the problem efficiently.

17. Final Code

class Solution {
    public char nthCharacter(int n) {

        long N = n;
        long digits = 1;
        long count = 9;
        long start = 1;

        while (N > digits * count) {
            N -= digits * count;

            digits++;
            count *= 10;
            start *= 10;
        }

        long number = start + (N - 1) / digits;

        int index = (int) ((N - 1) % digits);

        String str = String.valueOf(number);

        return str.charAt(index);
    }
}

Conclusion

The main trick in this problem is not to construct the infinite string.

Instead, divide the numbers into digit-length groups:

1–9
10–99
100–999
1000–9999
...

First, determine which group contains the nth character. Then calculate the exact number and finally the exact digit inside that number.

The important pattern to remember is:

1. Skip complete digit ranges
2. Find the target number
3. Find the digit inside that number

This gives an efficient:

Time:  O(log n)
Space: O(1)

solution.