Welcome to Subscribe On Youtube

Question

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

Given an integer n, return the nth 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 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.

 

Constraints:

  • 1 <= n <= 231 - 1

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

  • 
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';
        }
    }
}

############

class Solution {
    public int findNthDigit(int n) {
        int k = 1, cnt = 9;
        while ((long) k * cnt < n) {
            n -= k * cnt;
            ++k;
            cnt *= 10;
        }
        int num = (int) Math.pow(10, k - 1) + (n - 1) / k;
        int idx = (n - 1) % k;
        return String.valueOf(num).charAt(idx) - '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:
    def findNthDigit(self, n: int) -> int:
        k, cnt = 1, 9
        while k * cnt < n:
            n -= k * cnt
            k += 1
            cnt *= 10
        num = 10 ** (k - 1) + (n - 1) // k
        idx = (n - 1) % k
        return int(str(num)[idx])

############

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])


  • func findNthDigit(n int) int {
	k, cnt := 1, 9
	for k*cnt < n {
		n -= k * cnt
		k++
		cnt *= 10
	}
	num := int(math.Pow10(k-1)) + (n-1)/k
	idx := (n - 1) % k
	return int(strconv.Itoa(num)[idx] - '0')
}

  • /**
 * @param {number} n
 * @return {number}
 */
var findNthDigit = function (n) {
    let k = 1,
        cnt = 9;
    while (k * cnt < n) {
        n -= k * cnt;
        ++k;
        cnt *= 10;
    }
    const num = Math.pow(10, k - 1) + (n - 1) / k;
    const idx = (n - 1) % k;
    return num.toString()[idx];
};


  • public class Solution {
    public int FindNthDigit(int n) {
        int k = 1, cnt = 9;
        while ((long) k * cnt < n) {
            n -= k * cnt;
            ++k;
            cnt *= 10;
        }
        int num = (int) Math.Pow(10, k - 1) + (n - 1) / k;
        int idx = (n - 1) % k;
        return num.ToString()[idx] - '0';
    }
}

All Problems

All Solutions