400. Nth Digit

MediumMathBinary Search
Leetcode Link

Problem Description

The problem asks us to return the n^th digit of the concatenation of all positive integers in order. The sequence starts with 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... and goes on infinitely. Each number in the sequence is laid out consecutively to form an infinitely long number string. For example, if n equals 3, the function should return 3, as 3 is the third digit of the sequence. If n equals 11, we should return 0, which is the 11th digit in the sequence.

Intuition

Going digit by digit would be quite inefficient for large n, as the numbers grow larger and the sequence quickly becomes very long. A better method is to calculate the position of the target digit. Let’s break the problem into manageable parts:

  1. Determine the length of the number k where the n^th digit lies. Numbers with the same number of digits are in the same block (e.g., the number 12 belongs to the block where each number has two digits – 10 to 99).

  2. Calculate the actual number where our digit is present. Once we know the block where the digit is, we can compute the number itself.

  3. Determine the exact digit within that number which is our answer.

Here is the step-by-step approach based on the intuition mentioned:

  • We first find out the length k of the digits where n falls. Numbers with 1 digit are from 1 to 9, with 2 digits are from 10 to 99, and so on. We can figure out the count of all such numbers with k digits as 9 * 10^(k-1).

  • We iterate from length 1 upwards, subtracting the count of all the k-digit numbers from n until n is less than the count of the next set of numbers with k+1 digits. Each time we subtract, we're effectively skipping a whole block of digits.

  • After finding the length k of numbers where our digit is, we identify the number itself. We do this by adding 10^(k-1) to the result of (n-1)//k -- 10^(k-1) gets the first number of the block and (n-1)//k finds how far from the first number the target one is.

  • Finally, we find the n^th digit within the number we've identified. The index of our target digit in this number is (n-1)%k. We then convert the number to a string and retrieve our target digit using this index.

The given solution code follows these steps to find the answer in a time-efficient manner.

Learn more about Math and Binary Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Solution Approach

The implementation in the solution code follows the steps outlined in the intuition to find the n^th digit efficiently.

  1. Variables Initialization: k is initialized to 1, representing the length of numbers we're currently dealing with, and cnt is set to 9 because there are 9 numbers of length 1.

  2. While Loop to Determine Block:

    • The condition k * cnt < n is used to continue searching for the right block. If n is greater than the total number of digits in the current block (k * cnt), we advance to the next block of numbers with one more digit.
    • We subtract the number of digits in the current block from n with n -= k * cnt. This accounts for the digits we have skipped.
    • We then increase k by 1 to reflect the next block’s digit length.
    • The count cnt is multiplied by 10 to reflect the count for the next size of numbers (k+1 digits).

  3. Finding the Number: Once we know the correct block:

    • We calculate the actual number using num = 10 ** (k - 1) + (n - 1) // k. 10 ** (k - 1) gives us the starting number of the block. Then (n - 1) // k determines how many numbers into the block our target digit is.

  4. Determining the Exact Digit:

    • We calculate the index within the number where the n^th digit lies using idx = (n - 1) % k.
    • We convert the number num to a string and retrieve the target digit using return int(str(num)[idx]). The conversion to a string allows us to easily access any digit by its index.

  • Algorithm Usage: The implementation mainly involves arithmetic operations and string manipulation, which is an illustrative example of mathematical computing and iterative search techniques. It avoids brute force iteration by narrowing down the scope to the exact location of the desired digit.

  • Data Structures Used: No complex data structures are needed for this solution; basic integer and string operations suffice.

  • Patterns Used: The code employs a direct mathematical approach to determine the position rather than using search patterns or sorting methods.

The whole solution uses an efficient method to bypass a significant amount of unnecessary computation which would result from iterating through all the numbers in the sequence one by one. The core part of the solution hinges on understanding the pattern of digit lengths and being clever with arithmetic to pinpoint the exact location of the desired digit.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Example Walkthrough

Let's illustrate the solution approach with an example where n = 15. Our task is to determine the 15th digit in the concatenated sequence of positive integers.

Step 1: Determining the Length of Numbers

We initialize k to 1, which is the length of numbers we are currently considering, starting with numbers of length 1 (1 to 9). There are 9 such numbers, so cnt = 9.

  • Since n > k * cnt (15 > 1 * 9), it implies that the 15th digit is not in the first block of single-digit numbers.
  • Thus, we subtract the count of single-digit numbers from n: n -= 1 * 9, resulting in n = 6.
  • We increase k to 2 for the next block of numbers, which are double-digit numbers (10 to 99), and update cnt to 9 * 10 to reflect the count for the two-digit numbers.

Step 2: While Loop to Determine Block

  • Now k is 2 and cnt is 90. The condition 2 * 90 < 6 is not true, so we know that the 15th digit is within the block of two-digit numbers.

Step 3: Finding the Number

  • We calculate the number containing the 15th digit: num = 10 ** (2 - 1) + (6 - 1) // 2.
  • This gives us num = 10 + 2, because 10 is the first two-digit number and 2 is how many numbers into the two-digit block our target digit is. So, num = 12.

Step 4: Determining the Exact Digit

  • We then calculate the index within the number where the 15th digit lies: idx = (6 - 1) % 2.
  • The result is idx = 1, so we are looking for the second digit of the number num.
  • We convert num into a string and retrieve the target digit: int(str(num)[idx]).
  • This results in int(str(12)[1]), which evaluates to 2.

So, the algorithm tells us that the 15th digit in the concatenated sequence of positive integers is 2.

Solution Implementation

1class Solution:
2    def find_nth_digit(self, n: int) -> int:
3        # initialize variables
4        # 'digit_length' represents the current digit length we are calculating (e.g., 1 for 0-9, 2 for 10-99, etc.)
5        digit_length = 1
6      
7        # 'digit_count' represents the count of numbers that can be formed with the current 'digit_length'
8        digit_count = 9
9
10        # loop to find the correct digit length for the given 'n'
11        while digit_length * digit_count < n:
12            # subtract the total length covered so far
13            n -= digit_length * digit_count
14
15            # increment the digit length since we move on to numbers with more digits
16            digit_length += 1
17
18            # increase digit_count by a factor of 10 as we move to the next set of numbers
19            digit_count *= 10
20
21        # find the actual number where the result digit is located
22        number = 10 ** (digit_length - 1) + (n - 1) // digit_length
23
24        # find the index of the digit within 'number'
25        index_within_number = (n - 1) % digit_length
26
27        # get the digit at the calculated index of the number and return it
28        return int(str(number)[index_within_number])
29
30# Example usage:
31# sol = Solution()
32# result = sol.find_nth_digit(15)
33# print(result) # Output will be 2, which is the 15th digit in the sequence of the number "123456789101112131415..."
34
1class Solution {
2    public int findNthDigit(int n) {
3        // Initialize digit length `k` for numbers of k digits
4        // Initialize count `digitCount` for the count of numbers with `k` digits
5        int digitLength = 1;
6        int digitCount = 9;
7      
8        // Determine the range where the nth digit lies
9        while ((long) digitLength * digitCount < n) {
10            n -= digitLength * digitCount; // Reduce n by the number of positions we've covered
11            digitLength++;                 // Move to next digit length
12            digitCount *= 10;              // Increase the count for the next range of numbers
13        }
14      
15        // Calculate the actual number where the nth digit is from
16        int number = (int) Math.pow(10, digitLength - 1) + (n - 1) / digitLength;
17      
18        // Calculate the index within the number where the nth digit is located
19        int digitIndex = (n - 1) % digitLength;
20      
21        // Extract and return the nth digit from number
22        return String.valueOf(number).charAt(digitIndex) - '0';
23    }
24}
25
1#include <cmath> // Include cmath library to use pow function
2#include <string> // Include string library to convert number to string
3
4class Solution {
5public:
6    int findNthDigit(int n) {
7        // Define variables:
8        // k represents the number of digits in the numbers we're currently looking at
9        // digitCount represents the total number of digits for the current k digits wide numbers
10        int numDigits = 1;
11        long digitCount = 9;
12
13        // Loop to find the range in which n falls
14        // 1 * 9 digits for numbers with 1 digit
15        // 2 * 90 digits for numbers with 2 digits
16        // 3 * 900 digits for numbers with 3 digits and so on.
17        while (1ll * numDigits * digitCount < n) {
18            n -= numDigits * digitCount;
19            ++numDigits;
20            digitCount *= 10;
21        }
22
23        // Once the correct range is found, calculate the actual number where the nth digit is from
24        int number = pow(10, numDigits - 1) + (n - 1) / numDigits;
25
26        // Find the index within the number where the nth digit is located
27        int indexInNumber = (n - 1) % numDigits;
28
29        // Convert the number to a string to easily access any digit
30        string numberStr = to_string(number);
31
32        // Return the required digit converting it back to int
33        return numberStr[indexInNumber] - '0';
34    }
35};
36
1/**
2 * Find the nth digit of the infinite integer sequence.
3 * @param {number} n - The position of the digit to find in the sequence.
4 * @return {number} - The nth digit in the sequence.
5 */
6function findNthDigit(n: number): number {
7    let digitLength = 1; // The current number of digits we are getting through (1 for 0-9, 2 for 10-99, etc.)
8    let numberCount = 9; // The count of numbers that have digitLength digits (9 for one-digit numbers, 90 for two-digits, etc.)
9
10    // Loop to find the digitLength in which the nth digit is located
11    while (digitLength * numberCount < n) {
12        n -= digitLength * numberCount; // Decrease n by the number of digits covered in this step
13        digitLength += 1; // Increase the number length we are looking for
14        numberCount *= 10; // Increase the count to match the next number length
15    }
16
17    // Calculate the actual number where the nth digit is found
18    const startOfRange = Math.pow(10, digitLength - 1); // The first number with digitLength digits
19    const number = startOfRange + Math.floor((n - 1) / digitLength); // Identify the exact number
20
21    // Find the index within 'number' where the nth digit is located
22    const digitIndex = (n - 1) % digitLength;
23
24    // Convert the number to a string and get the digit at digitIndex
25    return parseInt(number.toString()[digitIndex]);
26}
27
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is a good use case for backtracking?

Time and Space Complexity

The time complexity of the given code is O(log n) because the while loop runs proportional to the number of digits in n. Each increase in the number of digits results in a ten-fold increase in the number range, thus the loop iterates through each digit length once, which is related logarithmically to n.

The space complexity is O(1) because there are a fixed number of integer variables (k, cnt, num, idx) used that do not grow with the input size n. The conversion of num to a string does not significantly affect the space complexity as it is related to the current k value (number of digits), which is a small constant for practical purposes.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used to implement recursion?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫