You are given the sequence: 0123456789101112131415...
The 0th digit of this sequence is 0, the 1st digit of this sequence is 1, the 2nd digit of this sequence is 2 and so on. You are given n, find the nth digit of the sequence.
 
Example 1:
Input: n = 12
Output: 1
Explanation: 1 is the 12th digit of the
given sequence.
Example 2:
Input: n = 20
Output: 4
Explanation: 4 is the 20th digit of the
given sequence.
 
Your Task:
You don't need to read or write anything. Your task is to complete the function NthDigit() which takes n as input parameter and returns the nth digit of the sequence.
 
Expected Time Complexity: O(log_{10}(n))
Expected Space Compelxity: O(1)
 
Constraints:
1 <= n <= 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Mathematics

Starter code: #User function Template for python3

class Solution:
	def NthDigit(self, n):
		# Code here

Solutions:
class Solution:

	def NthDigit(self, n):
		(cnt, r) = (0, 1)
		while True:
			cnt += r * pow(10, r - 1) * 9
			if cnt >= n:
				break
			r += 1
		cnt -= r * pow(10, r - 1) * 9
		n -= cnt
		(q, rem) = divmod(n, r)
		num = q + pow(10, r - 1) - 1
		if rem == 0:
			return num % 10
		else:
			num += 1
			ans = str(num)
			return int(ans[rem - 1])


class Solution:

	def NthDigit(self, n):
		if n <= 9:
			return n
		n += 1
		p = 10
		s = 10
		i = 2
		while True:
			t = p * i * 9
			s += t
			if s >= n:
				s -= t
				break
			i += 1
			p = p * 10
		d = n - s
		if d % i == 0:
			p = p + d // i - 1
			j = i
		else:
			p = p + d // i
			j = d % i
		j = i - j
		while j != 0:
			p = p // 10
			j -= 1
		return p % 10


class Solution:

	def NthDigit(self, n):
		if n <= 9:
			return n
		n += 1
		p = 10
		s = 10
		i = 2
		while True:
			t = p * i * 9
			s += t
			if s >= n:
				s -= t
				break
			i += 1
			p = p * 10
		d = n - s
		if d % i == 0:
			p = p + d // i - 1
			j = i
		else:
			p = p + d // i
			j = d % i
		j = i - j
		while j != 0:
			p = p // 10
			j -= 1
		return p % 10
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.NthDigit(n)
		print(ans)


class Solution:

	def NthDigit(self, n):
		if n < 10:
			return n
		digit = 0
		tmp = 0
		pre = 0
		while tmp < n:
			pre = tmp
			digit += 1
			tmp += 9 * 10 ** (digit - 1) * digit
		n -= pre
		num = 10 ** (digit - 1) + (n - 1) // digit
		index = (n - 1) % digit
		return num // 10 ** (digit - index - 1) % 10