Jobs

Interviews

Discussions

Nth Digit

#519 Most AskedMedium

Nth Digit #519 Most Asked

Medium

Bloomberg LP

27 views

Topics:

Math

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

Example 1:

Input: n = 3
Output: 3

Example 2:

Input: n = 11
Output: 0
Explanation: The 11^th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.

Constraints:

1 <= n <= 2³¹ - 1

Try coding it in LeetCode

Nth Digit

#519 Most AskedMedium

Nth Digit #519 Most Asked

Medium

Bloomberg LP

27 views

Topics:

Math

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

Example 1:

Input: n = 3
Output: 3

Example 2:

Input: n = 11
Output: 0
Explanation: The 11^th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.

Constraints:

1 <= n <= 2³¹ - 1

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible value of 'n'? Is it within the range of a 32-bit integer?
Should I assume that 'n' will always be a positive integer greater than zero?
Could you provide a few more examples, especially for larger values of 'n', to confirm my understanding of the problem?
Is there a specific return value that you would prefer if no digit can be found for the given 'n'? For example, should I throw an exception or return a specific value such as -1?
Are there any specific performance considerations or time complexity targets I should aim for, given the potential range of 'n'?

Brute Force Solution

Approach

We want to find a specific digit in a sequence of numbers. The brute force way is to just write out all the numbers one after another until we reach the digit we are looking for. Then we can simply pick that digit out.

Here's how the algorithm would work step-by-step:

Start writing numbers down, beginning with 1, then 2, then 3, and so on.
Keep a count of how many digits we have written so far.
For each number, determine how many digits it has (for example, 10 has two digits).
Add the number of digits of the current number to the total digit count.
Check if the total digit count is now greater than or equal to the target number we're looking for.
If it is, we've gone far enough. Figure out which digit of the current number is the one we need by counting backwards from the total digit count.
That digit is our answer.

Code Implementation

def find_nth_digit_brute_force(n):
    digit_count = 0
    number = 1

    while True:
        number_string = str(number)
        number_length = len(number_string)

        # Update total digit count
        digit_count += number_length

        # Check if we have passed the nth digit
        if digit_count >= n:

            # Calculate the index of the target digit
            index_of_digit = number_length - (digit_count - n) - 1

            # Return the target digit
            return int(number_string[index_of_digit])

        number += 1

Big(O) Analysis

Time Complexity

O(log(n)) – The algorithm iterates through number ranges (1-9, 10-99, 100-999, etc.) to find the correct range containing the nth digit. The number of digits in each range grows, and the number of ranges we check is proportional to the number of digits in the final number. Determining the number of digits and then the digit itself takes constant time. Therefore, the dominant factor is the number of ranges, which grows logarithmically with n, resulting in a time complexity of O(log(n)).

Space Complexity

O(1) – The provided algorithm primarily uses a few integer variables to track the current number, the digit count, and potentially some temporary calculations. No auxiliary data structures like arrays, lists, or hash maps are created to store intermediate results. Therefore, the space used by the algorithm remains constant irrespective of the input 'N' (the target digit index). This constant space usage results in a space complexity of O(1).

Optimal Solution

Approach

The goal is to find a single digit within a sequence of increasing numbers written out one after another. Instead of building the entire sequence, we determine which number contains the nth digit, and then extract that digit.

Here's how the algorithm would work step-by-step:

First, figure out how many digits long the number we're looking for is. We do this by checking the ranges of 1-digit numbers, 2-digit numbers, 3-digit numbers, and so on, until we find the range that contains our target digit.
Next, determine which actual number contains the target digit. Once we know how many digits the number has, we can calculate which specific number in that range has the nth digit by using math to skip through the range.
Finally, extract the correct digit from the number we found. Convert the number to a string of characters, and then grab the digit we need based on the remaining position calculated in the previous step.

Code Implementation

def find_nth_digit(n):
    digit_length = 1
    count_of_numbers = 9
    
    while n > digit_length * count_of_numbers:
        n -= digit_length * count_of_numbers
        digit_length += 1
        count_of_numbers *= 10

    # Determine which number contains the nth digit.
    starting_number = 10 ** (digit_length - 1)
    number_index = (n - 1) // digit_length
    target_number = starting_number + number_index
    
    # Calculate the index of the digit within the number.
    digit_index = (n - 1) % digit_length
    
    target_number_string = str(target_number)

    # Extract the correct digit from the number.
    return int(target_number_string[digit_index])

Big(O) Analysis

Time Complexity

O(log n) – The algorithm iteratively determines the digit length of the number containing the nth digit. This process involves checking ranges of numbers with increasing digit lengths (1-digit, 2-digit, 3-digit, etc.). The number of iterations corresponds to the number of digits required, which grows logarithmically with n. After finding the digit length, the algorithm performs constant-time arithmetic operations to identify the specific number and extract the desired digit. Therefore, the dominant factor is the logarithmic search for the digit length, resulting in O(log n) time complexity.

Space Complexity

O(1) – The space complexity is constant because the algorithm uses a fixed number of variables regardless of the input n. The algorithm calculates the digit length, the number containing the digit, and the index of the digit within the number using variables like 'digits', 'start', and 'index'. These variables take up a constant amount of space. The conversion of the target number to a string is temporary and its length is bounded by the number of digits in the final number, which is related to the number of digits being checked and can be considered constant relative to the input n. No additional data structures scale with the input n are used.

Edge Cases

Case	How to Handle
n = 0	Since n is a positive integer, treat n=0 as an invalid input and throw an exception or return -1.
n = 1	Return 1 directly, as the first digit is '1'.
n is a large number, close to Integer.MAX_VALUE, causing potential integer overflow during calculations of digit count.	Use long data type to store intermediate calculations, such as the number of digits and the base value to prevent integer overflow.
n is within the range of single-digit numbers (1-9)	Directly return n as an integer, since it represents the nth single digit number.
n is within the range of double-digit numbers (10-99)	Calculate the offset within the double-digit range and extract the corresponding digit.
n is very large such that efficient calculation becomes crucial	Optimize the digit counting loop to quickly skip over ranges of numbers (1-digit, 2-digit, 3-digit, etc.) before narrowing down to the target number.
n such that resulting number has leading zeros	Leading zeros are not applicable to this problem because we are dealing with the sequence of positive integers, which don't have leading zeros by definition.
No valid solution exists (theoretically impossible for positive n)	Since 'n' is defined as a positive integer, a valid solution should always exist, but a check for n<1 could be included as a defensive measure, though not strictly necessary, and handled by returning an error value or exception.

n = 0

How to Handle:

Since n is a positive integer, treat n=0 as an invalid input and throw an exception or return -1.

n = 1

How to Handle:

Return 1 directly, as the first digit is '1'.

n is a large number, close to Integer.MAX_VALUE, causing potential integer overflow during calculations of digit count.

How to Handle:

Use long data type to store intermediate calculations, such as the number of digits and the base value to prevent integer overflow.

n is within the range of single-digit numbers (1-9)

How to Handle:

Directly return n as an integer, since it represents the nth single digit number.

n is within the range of double-digit numbers (10-99)

How to Handle:

Calculate the offset within the double-digit range and extract the corresponding digit.

n is very large such that efficient calculation becomes crucial

How to Handle:

Optimize the digit counting loop to quickly skip over ranges of numbers (1-digit, 2-digit, 3-digit, etc.) before narrowing down to the target number.

n such that resulting number has leading zeros

How to Handle:

Leading zeros are not applicable to this problem because we are dealing with the sequence of positive integers, which don't have leading zeros by definition.

No valid solution exists (theoretically impossible for positive n)

How to Handle:

Since 'n' is defined as a positive integer, a valid solution should always exist, but a check for n<1 could be included as a defensive measure, though not strictly necessary, and handled by returning an error value or exception.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum possible value of 'n'? Is it within the range of a 32-bit integer?
Should I assume that 'n' will always be a positive integer greater than zero?
Could you provide a few more examples, especially for larger values of 'n', to confirm my understanding of the problem?
Is there a specific return value that you would prefer if no digit can be found for the given 'n'? For example, should I throw an exception or return a specific value such as -1?
Are there any specific performance considerations or time complexity targets I should aim for, given the potential range of 'n'?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start writing numbers down, beginning with 1, then 2, then 3, and so on.
Keep a count of how many digits we have written so far.
For each number, determine how many digits it has (for example, 10 has two digits).
Add the number of digits of the current number to the total digit count.
Check if the total digit count is now greater than or equal to the target number we're looking for.
If it is, we've gone far enough. Figure out which digit of the current number is the one we need by counting backwards from the total digit count.
That digit is our answer.

Code Implementation

def find_nth_digit_brute_force(n):
    digit_count = 0
    number = 1

    while True:
        number_string = str(number)
        number_length = len(number_string)

        # Update total digit count
        digit_count += number_length

        # Check if we have passed the nth digit
        if digit_count >= n:

            # Calculate the index of the target digit
            index_of_digit = number_length - (digit_count - n) - 1

            # Return the target digit
            return int(number_string[index_of_digit])

        number += 1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, figure out how many digits long the number we're looking for is. We do this by checking the ranges of 1-digit numbers, 2-digit numbers, 3-digit numbers, and so on, until we find the range that contains our target digit.
Next, determine which actual number contains the target digit. Once we know how many digits the number has, we can calculate which specific number in that range has the nth digit by using math to skip through the range.
Finally, extract the correct digit from the number we found. Convert the number to a string of characters, and then grab the digit we need based on the remaining position calculated in the previous step.

Code Implementation

def find_nth_digit(n):
    digit_length = 1
    count_of_numbers = 9
    
    while n > digit_length * count_of_numbers:
        n -= digit_length * count_of_numbers
        digit_length += 1
        count_of_numbers *= 10

    # Determine which number contains the nth digit.
    starting_number = 10 ** (digit_length - 1)
    number_index = (n - 1) // digit_length
    target_number = starting_number + number_index
    
    # Calculate the index of the digit within the number.
    digit_index = (n - 1) % digit_length
    
    target_number_string = str(target_number)

    # Extract the correct digit from the number.
    return int(target_number_string[digit_index])

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n = 0	Since n is a positive integer, treat n=0 as an invalid input and throw an exception or return -1.
n = 1	Return 1 directly, as the first digit is '1'.
n is a large number, close to Integer.MAX_VALUE, causing potential integer overflow during calculations of digit count.	Use long data type to store intermediate calculations, such as the number of digits and the base value to prevent integer overflow.
n is within the range of single-digit numbers (1-9)	Directly return n as an integer, since it represents the nth single digit number.
n is within the range of double-digit numbers (10-99)	Calculate the offset within the double-digit range and extract the corresponding digit.
n is very large such that efficient calculation becomes crucial	Optimize the digit counting loop to quickly skip over ranges of numbers (1-digit, 2-digit, 3-digit, etc.) before narrowing down to the target number.
n such that resulting number has leading zeros	Leading zeros are not applicable to this problem because we are dealing with the sequence of positive integers, which don't have leading zeros by definition.
No valid solution exists (theoretically impossible for positive n)	Since 'n' is defined as a positive integer, a valid solution should always exist, but a check for n<1 could be included as a defensive measure, though not strictly necessary, and handled by returning an error value or exception.

n = 0

How to Handle:

Since n is a positive integer, treat n=0 as an invalid input and throw an exception or return -1.

n = 1

How to Handle:

Return 1 directly, as the first digit is '1'.

n is a large number, close to Integer.MAX_VALUE, causing potential integer overflow during calculations of digit count.

How to Handle:

Use long data type to store intermediate calculations, such as the number of digits and the base value to prevent integer overflow.

n is within the range of single-digit numbers (1-9)

How to Handle:

Directly return n as an integer, since it represents the nth single digit number.

n is within the range of double-digit numbers (10-99)

How to Handle:

Calculate the offset within the double-digit range and extract the corresponding digit.

n is very large such that efficient calculation becomes crucial

How to Handle:

Optimize the digit counting loop to quickly skip over ranges of numbers (1-digit, 2-digit, 3-digit, etc.) before narrowing down to the target number.

n such that resulting number has leading zeros

How to Handle:

Leading zeros are not applicable to this problem because we are dealing with the sequence of positive integers, which don't have leading zeros by definition.

No valid solution exists (theoretically impossible for positive n)

How to Handle:

0/1037 Bloomberg LP questions completed

0/1037 completed