400. Nth Digit #

Problem #

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 <= int(math.Pow(2, 31)) - 1

Problem Summary #

Given an integer n, find and return the nth digit in the infinite integer sequence [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …].

Solution Approach #

• When bits = 1, there are these 9 numbers: 1,2,3,4,5,6,7,8,9; 9 = math.Pow10(bits - 1) * bits

• When bits = 2, there are these 90 numbers: 10-99; 90 = math.Pow10(bits - 1) * bits

• Continuously subtract from n the total number of digits starting from bits = 1, to find how many digits the number containing n has, namely bits

• Calculate the number num that contains n, which equals the initial value plus (n - 1) / bits

• Calculate which digit digitIdx within this number contains n, equal to (n - 1) % bits

• Calculate the digit at digitIdx

  Take 11 as an example: #

  11 - 9 = 2

  (2 - 1) / 2 = 0

  (2 - 1) % 2 = 1

  That is to say, the 11th digit is the second digit of the first number whose digit count is 2, which is 0

Code #

package leetcode

import "math"

func findNthDigit(n int) int {
	if n <= 9 {
		return n
	}
	bits := 1
	for n > 9*int(math.Pow10(bits-1))*bits {
		n -= 9 * int(math.Pow10(bits-1)) * bits
		bits++
	}
	idx := n - 1
	start := int(math.Pow10(bits - 1))
	num := start + idx/bits
	digitIdx := idx % bits
	return num / int(math.Pow10(bits-digitIdx-1)) % 10
}