Question

Formatted question description: https://leetcode.ca/all/400.html

 Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...

 Note:
 n is positive and will fit within the range of a 32-bit signed integer (n < 231).

 Example 1:

 Input:
 3

 Output:
 3


 Example 2:

 Input:
 11

 Output:
 0

 Explanation:
 The 11th 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.

Algorithm

Define a variable cnt, initialize it to 9, and then expand by 10 times each loop, and use a variable len to record the number of digits in the current loop interval, and another variable start is needed to record the current loop interval The first number.

We subtract len*cnt (the total number of digits in the interval) every time we loop. When n falls into a certain interval, then (n-1)/len is the coordinate of the target number in that interval, plus The start is to get the target number, and then we convert the target number start into a string, (n-1)%len is the required target bit.

Finally, don’t forget to consider the int overflow problem.

Code

Java

  • 
    public class Nth_Digit {
    
    
        class Solution {
            public int findNthDigit(int n) {
    
                if (n <= 0) {
                    return 0;
                }
    
                long len = 1;
                long start = 1;
                long BATCH_COUNT_FOR_LEN = 9;
    
                while (n > len * BATCH_COUNT_FOR_LEN) {
                    n -= len * BATCH_COUNT_FOR_LEN;
    
                    len++;
                    start *= 10;
                    BATCH_COUNT_FOR_LEN *= 10;
                }
    
                // find n-digit is at which number
                long number = start + (n - 1) / len;
                String numberInString = String.valueOf(number);
    
                return numberInString.charAt((int)((n - 1) % len)) - '0';
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/nth-digit/
    // Time: O(lgN)
    // Space: O(1)
    class Solution {
    public:
        int findNthDigit(int n) {
            long long len = 1, p = 1, cnt = 9;
            while (n > cnt) {
                n -= cnt;
                ++len;
                cnt = 9 * len * (p *= 10);
            }
            int k = p + (n - 1) / len, r = (n - 1) % len, i = len - r - 1;
            while (i--) k /= 10;
            return k % 10;
        }
    };
    
  • class Solution(object):
      def findNthDigit(self, n):
        """
        :type n: int
        :rtype: int
        """
        start, size, step = 1, 1, 9
        while n > size * step:
          n -= size * step
          size += 1
          start *= 10
          step *= 10
        return int(str(start + (n - 1) // size)[(n - 1) % size])
    
    

All Problems

All Solutions