Math is a fun part 2

Math problems are not that simple and need lots of practice.

400. Nth Digit

Nth Digit - LeetCode

My own version has a bug. I have to fix the bug when I am available.

class Solution:
    def findNthDigit(self, n: int) -> int:
        if n<=9:return n
        length = 1
        digit = 0
        pre_number = 0
        
        while True:
            this_number = 10**length-pre_number
            new_digit =digit+ (this_number)*length
            #print('l, n', length, new_digit)
            if new_digit>=n+1:
                offset = n-digit
                #print('offset', offset)
                a, b = offset//length, offset%length
                #print('a,b,length', a,b,length)
                this_num = '1'+'0'*(length-1)
                this_num = int(this_num)+a
                #print(this_num)
                return int(str(this_num)[b])
            digit = new_digit
            length += 1

Code from Stephan.

class Solution:
    def findNthDigit(self, n: int) -> int:
        n -= 1
        for digits in range(1, 11):
            first = 10**(digits - 1)
            if n < 9 * first * digits:
                return int(str(first + n/digits)[n%digits])
            n -= 9 * first * digits

A very nice explanation from

https://leetcode.com/problems/nth-digit/discuss/88363/Java-solution/93222

1 ~ 9 include 9 one digit number;
10 ~ 99 include 90 two digits number;
100 ~ 999 include 900 three digits number;
1000 ~ 9999 include 9000 four digits number;
...

len is how many digits:1 or 2 or 3 ..., range is 9 or 90 or 900 ...

public int findNthDigit(int n) {
		int len = 1, i = 1;
		long range = 9;
		while(n > len * range){
			n -= len * range;
			len++;
			range *= 10;
			i *= 10;
		}
		i += (n - 1) / len;
		String s = Integer.toString(i);
		return Character.getNumericValue(s.charAt((n - 1) % len));
	}

Above code is in java. Here is a c++ version

https://leetcode.com/problems/nth-digit/discuss/88363/Java-solution/367904

In C++

int findNthDigit(int n) {
        long step=9;
        int size=1, start=1;
        while(size*step < n)
        {
            n     -= size*step;
            size  += 1;
            step  *= 10; // 9, 90, 900, 9000, ...
            start *= 10; // 1, 10, 100, 1000, ...
        }
        
        int number = (n-1)/size + start;
        return to_string(number)[(n-1)%size] - '0';
    }

Naive python

class Solution:
    def findNthDigit(self, n: int) -> int:
        if n<=9:return n
        length = 2
        digits = 9
        delta = 9
        begin = 1
        while True:
            delta *= 10
            #delta 9 90 900 9000
            begin *= 10
            # begin 1 10 100 1000
            new_digits =digits+ delta*length
            if new_digits>=n:
                offset = n -1- digits
                a, b = offset//length, offset%length
                this_num = begin + a
                return str(this_num)[b]
            else:
                digits = new_digits
                length += 1

More concise python

class Solution:
    def findNthDigit(self, n: int) -> int:
        start, length, cnt_len_k = 1, 1, 9
        while length*cnt_len_k < n:
            n -= length*cnt_len_k
            length += 1
            cnt_len_k *= 10 #9, 90, 900, 9000, ...
            start *= 10 #1, 10, 100, 1000, ...
        number = start + (n-1)//length
        return str(number)[(n-1)%length]