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

&nbsp;
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.


&nbsp;
Constraints:


	1 &lt;= n &lt;= 231 - 1


class Solution:
    def findNthDigit(self, n: int) -> int:
        low, high = 1, 0
        place = 1
        
        sum_ = 0
        
        while True:
            high = 10**place -1
            digits_sum = (high - low +1 ) * place
            
            if sum_<= n <= digits_sum + sum_:
                break
            else:
                low = high+1
                sum_+= digits_sum
            place += 1
        
        remaining_digits = n - sum_
        
        position = (remaining_digits-1)//place 
        index_ =  remaining_digits - position*place -1
        
        
        number = low + position
        # return str(number)[index_]
        count = 0
        index_ = place - 1 - index_
        l = []
        # 
        while number:
            if count == index_:
                return number%10
            number = number//10
            count+=1
class Solution {
    public int findNthDigit(int n) {

        if(n < 10)
            return n;

        long currDigitIndex = 10;
        int tillNextIncrease = 90;
        int currNumberSize = 2;
        int currNumber = 10;
        int next = tillNextIncrease;

        while(currDigitIndex < n) {

            currNumber++;
            currDigitIndex += currNumberSize;
            next--;

            if(next == 0) {
                currNumberSize++;
                tillNextIncrease *= 10;
                next = tillNextIncrease;
            }
        }

        int nthDigit = currNumber % 10;
        if(currDigitIndex == n) {
            while(currNumber != 0) {
                nthDigit = currNumber % 10;
                currNumber /= 10;
            }
        } else if(currDigitIndex > n) {

            currNumber--;

            while(currDigitIndex > n) {
                currDigitIndex--;
                nthDigit = currNumber % 10;
                currNumber /= 10;
            }
        }

        return nthDigit;
    }
}
class Solution {
public:
    #define ll long long 
    int findNthDigit(int n) {
        if(n<=9) return n;
        ll i=1;
        ll sum=0;
        while(true){
            ll a=(9*pow(10,i-1))*i;
            if(n-a<0){
                break;
            } 
            else{
                sum+=9*pow(10,i-1);
                n-=a;
            }
            i++;
        }
        
        ll x=0;        
        ll mod=n%i;
        n=(n/i);
        n+=sum;
        if(mod==0) return n%10;
        else{
            n++;
            ll x=i-mod;
            while(x--){
                n/=10;
            }
        }
        return n%10;
    }
};
var findNthDigit = function(n) {
    var len = 1;
    var range = 9;
    var base = 1;
    while(n>len*range)
    {
        n -= len *range;
        range *= 10;
        base *= 10;
        len++;
    }
    // [100, 101, 102,...]
    // 100 should have offset 0, use (n-1) to make the counting index from 0-based.
    var num = base + Math.floor((n-1)/len);
    var s = num.toString();
    return parseInt(s[(n-1)%len]);
};
Nth Digit