LeetCode 400 - Nth Digit

https://leetcode.com/problems/nth-digit/

Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...

Note:
n is positive and will fit within the range of a 32-bit signed integer (n < 231).

Example

Input:
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.

http://www.cnblogs.com/grandyang/p/5891871.html
这道题还是蛮有创意的一道题，是说自然数序列看成一个长字符串，问我们第N位上的数字是什么。那么这道题的关键就是要找出第N位所在的数字，然后可以把数字转为字符串，这样直接可以访问任何一位。那么我们首先来分析自然数序列和其位数的关系，前九个数都是1位的，然后10到99总共90个数字都是两位的，100到999这900个数都是三位的，那么这就很有规律了，我们可以定义个变量cnt，初始化为9，然后每次循环扩大10倍，再用一个变量len记录当前循环区间数字的位数，另外再需要一个变量start用来记录当前循环区间的第一个数字，我们n每次循环都减去len*cnt (区间总位数)，当n落到某一个确定的区间里了，那么(n-1)/len就是目标数字在该区间里的坐标，加上start就是得到了目标数字，然后我们将目标数字start转为字符串，(n-1)%len就是所要求的目标位，最后别忘了考虑int溢出问题，我们干脆把所有变量都申请为长整型的好了
https://leetcode.com/problems/nth-digit/discuss/88363/java-solution

Straight forward way to solve the problem in 3 steps:

1. find the length of the number where the nth digit is from
2. find the actual number where the nth digit is from
3. find the nth digit and return

 public int findNthDigit(int n) {
  int len = 1;
  long count = 9;
  int start = 1;

  while (n > len * count) {
   n -= len * count;
   len += 1;
   count *= 10;
   start *= 10;
  }

  start += (n - 1) / len;
  String s = Integer.toString(start);
  return Character.getNumericValue(s.charAt((n - 1) % len));
 }

https://www.jianshu.com/p/73ae878eb3e9

这么一来，要找到第n个数，首先要知道这个数所在的序列中的数字是什么，我们只能先判断当前的是几位数，因为每多一位数，其范围内的数字个数会变成上一轮的10倍，比如个位数有9个，两位数有90个，三位数有900个。。。两位数对应的数字有902个，三位数有9003个，所以可以通过这个规律先判断要找的序列数字是几位数。
找出是几位数后，在通过对位数的除法得出数字是多少，比如如果n是12，那么先通过其大于9，小于90*2+9，得知是两位数，然后通过（12-9）/2 = 1得出其至少是9+1，也就是10或者10以后的数字，具体是10还是11，要看有没有余数，这里（12-9）%2=1，所以余数为1，也就是超过了10，是10的后一个数字的第一个数。其实这里很简单我们直接就可以知道是11中的第一个1。
如果余数是0，说明就是当前找到的数字的最后一位，直接将该数字对10取余即可得到需要的个位数字。如果余数大于0，说明是下一个序列数字中的数，然后根据余数来判断是下个序列数字中的第几个数。要得到一个多位数中的某位数，有多种做法，一种是化为字符数组直接取，另一种我用的是先取余再做除法，比如要得到1245这个数字中的第三个数字4，先让其对100取余数得到45，然后对10做触发得到4。至于怎么知道是100和10，就可以通过是第几位来进行10的次方运算了，这个直接看到代码就可以明白，只是有点长，要想清楚。
还有一点要注意的是，提交时我在一个很大的数上出了错，因为题目给的n的范围是小于2的31次方，这个数字在上述处理过程中可能会有大到超过int型变量范围的数字，因此不得不全部使用了long型变量表示数字。另外Math.pow()这个次方计算操作的两个参数必须是double型的，因此也不得不进行了强制转换又转换。

    public int findNthDigit(int n) {
        if (n <= 9) return n;
        
        long lastNum = 9;
        long reduce = 9;
        long num = 90;
        long i = 2;
        while (n > reduce + num * i) {
            lastNum = lastNum + num;
            reduce = reduce + num * i;
            num = num * 10;
            i++;
        }
        long over = (long)n - reduce;
        System.out.println(lastNum + over / i);
        long index = over / i;
        long reste = over % i;
        if (reste == 0) return (int)((lastNum + index) % 10);
        else return (int)(((lastNum + index + 1) % (long)Math.pow(10.0, (double)(i - reste + 1))) / (long)Math.pow(10.0, (double)(i - reste)));
    }

https://leetcode.com/problems/nth-digit/discuss/88400/Just-explain-no-code

sequence 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5 1 6
Nth digital 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

I list sequence 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
blow the sequence is the Nth digital, like the 11th digital is 0, 12 is 1, 13 is 1, 14 is 1, 15 is 2, 16 is 1, 17 is 3.........

Sot ehe regular is very oberviously now:
1-------9 9*1 = 9 digits
10-----99 90 *2 = 180 digits
100---999 900 * 3 = 2700 digits

Now, for example gave N = 1000, then 1000-9-180 = 811, it means the 811th digit local in [100, 999], and we know each number like 100 has three digit, so 811 / 3 = 270,

Then, we know the 270th number in [100, 999], is 270th + 100 (start from 100) = 370.

370 still has three digit, which one is the answer? 3, 7, 0

811 % 3 = 1, so the first one is the answer, so return 3

https://leetcode.com/problems/nth-digit/discuss/88369/0ms-C%2B%2B-Solution-with-Detail-Explanation

To make the problem much much more easier, I divide the problem into 3 parts:

1. calculate how many digits the number has.
2. calculate what the number is.
3. find out which digit in the number is we wanted.

You can find the relative code part in the code section.
Here is an example to help you to understand my code:

Example:

• Input: 250
• After step 1, you will find that the 250th digit must belong to a 3-digit number, since 1~9 can only provide 9 digits and 10~99 can only provide 180 digits. Here, n = 250 - 9 - 90 * 2 = 61, and digits = 3.
• In step 2, we will find the target number, which named as number in my code. From step 1, the n becomes to 61, which means "the 61st digit in 3-digit number is the digit we are looking for ." Easily, we know the 61st digit in 3-digit number belongs to number = 100 + 61 / 3 = 100 + 20 = 120. index is the index of the target digit in number. If index equals to 0, it means the target digit is the last digit of number.
• Step 3, from step 2, we know index = n % digits = 61 % 3 = 1, which means the target digit is the 1st digit in number. Then, return 1.

Code:

    int findNthDigit(int n) 
    {
        // step 1. calculate how many digits the number has.
        long base = 9, digits = 1;
        while (n - base * digits > 0)
        {
            n -= base * digits;
            base *= 10;
            digits ++;
        }

        // step 2. calculate what the number is.
        int index = n % digits;
        if (index == 0)
            index = digits;
        long num = 1;
        for (int i = 1; i < digits; i ++)
            num *= 10;
        num += (index == digits) ? n / digits - 1 : n / digits;;

        // step 3. find out which digit in the number is we wanted.
        for (int i = index; i < digits; i ++)
            num /= 10;
        return num % 10;
    }

https://leetcode.com/problems/nth-digit/discuss/88375/Short-Python%2BJava
Check the same-length ranges 1-9, 10-99, 100-999, 1000-9999, etc.

public int findNthDigit(int n) {
    n -= 1;
    int digits = 1, first = 1;
    while (n / 9 / first / digits >= 1) {
        n -= 9 * first * digits;
        digits++;
        first *= 10;
    }
    return (first + n/digits + "").charAt(n%digits) - '0';
}

https://discuss.leetcode.com/topic/59314/java-solution/6

1位数到n位数共有多少个数字可以先计算出来写在程序中,

2 3 4 5 6 7 8 9 10

int main () {     long long sum = 0;     for(int i = 0;; i++){         long long t = 9 * (long long)pow(10, i) * (i + 1);         if(t > INT_MAX) break;         sum += t;         cout<<i<<':'<<t<<" sum:"<<sum<<endl;     }     return 0; }

class Solution {

    int arr[9] = {0, 9, 189, 2889, 38889, 488889, 5888889, 68888889, 788888889};

public:

    int findNthDigit(int n) {

        int index;

        for(index = 0; index < 9 && arr[index] < n; index++); // 确定位数

        int t = (n - arr[index - 1] - 1);

        int num = (t / index) + (int)pow(10, index - 1); // 确定数

        int p = index - (t % index) - 1; // 确定第几位

        for(int i = 0; i < p; i++){ // 找出该位

            num /= 10;

        }

        return num % 10; // 个位为我们要找的数

    }

};