Leetcode 400. Nth Digit
Problem Explanation
The question asks us to figure out the digit which is in the nth position in a sequentially arranged string. So if we're handing over 'n' as an integer to our function, it will return the 'nth' digit in the sequence of natural numbers from 1 to infinity put together.
"3" would return '3', as it's the third digit in the string: '12345678910...' "11" would return '0', as '0' is the 11th digit in the infinity string: '1234567891011...'
We must note, however, that the function should work with very large numbers of 'n' - it should be able to handle any 32-bit signed integer.
Approach
The main idea is to find the actual number that contains the nth digit and its corresponding digit position. In order to do so, we need to know how many digits are there within a number range. For instance, there are 9 one-digit numbers, 90 two-digit numbers, 900 three-digit numbers, and so on. On encountering such digit lengths in increasing order, we can skip blocks of numbers until we reach the one containing the target nth digit.
We traverse the ranges until we figure out the range where the nth digit is. For example, if n = 189, we first subtract 91, then 902, and we know that the 189th digit is in the third range. We figure out the actual number using digitSize, and finally, we find out the exact digit in that number.
Let's walk through our approach with an example: n = 15
The 15th digit of the sequence 1, 2, 3, ..., 9, 10, 11, 12, 13... is found in the range of two-digit numbers, ie., between 10 and 99. Hence, 'digitSize' is 2 and 'startNum' is 10. 'n' is decremented by the count of digits until it reaches the range containing the nth digit. Here, 'n' becomes 6 (15-9). Finally, we locate the number having the nth digit (startNum+(nโ1)/digitSize) and the index of the nth digit in that number (nโ1)%digitSize.
Python Solution
1 2python 3class Solution: 4 def findNthDigit(self, n: int) -> int: 5 digitSize = 1 6 startNum = 1 7 count = 9 8 9 while n > digitSize * count: 10 n -= digitSize * count 11 digitSize += 1 12 startNum *= 10 13 count *= 10 14 15 startNum += (n - 1) // digitSize 16 return int(str(startNum)[(n - 1) % digitSize])
Java Solution
1 2java 3class Solution { 4 public int findNthDigit(int n) { 5 int digitSize = 1; 6 long startNum = 1; 7 long count = 9; 8 9 while (digitSize * count < n) { 10 n -= digitSize * count; 11 digitSize++; 12 startNum *= 10; 13 count *= 10; 14 } 15 16 int targetNum = (int) (startNum + (n - 1) / digitSize); 17 int index = (n - 1) % digitSize; 18 return Integer.parseInt(Integer.toString(targetNum).substring(index, index + 1)); 19 } 20}
JavaScript Solution
1 2javascript 3var findNthDigit = function(n) { 4 let digitSize = 1; 5 let startNum = 1; 6 let count = 9; 7 8 while(n > digitSize * count){ 9 n -= digitSize * count; 10 digitSize++; 11 startNum *= 10; 12 count *= 10; 13 } 14 15 startNum += (n - 1) / digitSize; 16 return String(startNum)[(n - 1) % digitSize]; 17};
C++ Solution
1 2c++ 3class Solution { 4public: 5 int findNthDigit(int n) { 6 int digitSize = 1; 7 long startNum = 1; 8 long count = 9; 9 10 while (digitSize * count < n) { 11 n -= digitSize * count; 12 digitSize++; 13 startNum *= 10; 14 count *= 10; 15 } 16 17 int targetNum = startNum + (n - 1) / digitSize; 18 int index = (n - 1) % digitSize; 19 return to_string(targetNum)[index] - '0'; 20 } 21};
C# Solution
1 2CSharp 3public class Solution { 4 public int FindNthDigit(int n) { 5 int digitSize = 1; 6 long count = 9; 7 int startNum = 1; 8 9 while (n > digitSize * count) { 10 n -= (int) (digitSize * count); 11 digitSize += 1; 12 startNum *= 10; 13 count *= 10; 14 } 15 16 startNum += (n - 1) / digitSize; 17 string s = startNum.ToString(); 18 return (int)Char.GetNumericValue(s[(n - 1) % digitSize]); 19 } 20}
Ruby Solution
The Ruby solution is also very similar to the given Python, Java, JavaScript, and C++ solutions. You start by initialising digitSize = 1
, startNum = 1
, and count = 9
. Then you use a while loop to decrease n
until it is less than digitSize * count
. After finding the range containing the n
th digit, you locate the number that has the n
th digit and find the index of the n
th digit in that number. Here is the Ruby solution code:
1 2ruby 3def findNthDigit(n) 4 digitSize = 1 5 startNum = 1 6 count = 9 7 8 while n > digitSize * count 9 n -= digitSize * count 10 digitSize += 1 11 startNum *= 10 12 count *= 10 13 end 14 15 startNum += (n - 1) / digitSize 16 return startNum.to_s[(n - 1) % digitSize].to_i 17end
This will return the n
th digit of the infinite integer array.
Go Solution
Here, the Go solution is also provided which is similar to the solutions of other languages. Firstly, you start by initialising the variables digitSize, startNum and count to 1, 1, and 9 respectively. After that, you decrease the value of 'n' until it's less than 'digitSize * count'. Then you try to find the range in which 'n'th digit is. Find the exact number that contains 'n'th digit and finally find the 'n'll digit's index in that number.
1
2go
3func findNthDigit(n int) int {
4 digitSize := 1
5 startNum := 1
6 count := 9
7
8 for n > digitSize*count {
9 n -= digitSize * count
10 digitSize++
11 startNum *= 10
12 count *= 10
13 }
14
15 startNum += (n - 1) / digitSize
16 return int(strconv.Itoa(startNum)[(n-1)%digitSize] - '0')
17}
This function returns the n'th digit of the number sequence from 1 to infinity as an integer.
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.