400. Nth Digit.md

400. Nth Digit

---

Difficulty : Medium

Related Topics : Math

---

Find the n^th 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 < 2³¹).

Example 1:

Input:
3

Output:
3

Example 2:

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.

---

Solution

• mine
  • Java
    • Runtime: 0 ms, faster than 100.00%, Memory Usage: 36.6 MB, less than 6.12% of Java online submissions

      //O(1)time
      //O(1)space
      public int findNthDigit(int n) {
          int i = 1;
          long m = 9;
          //find the last number length
          while (n > m) {
              i++;
              n -= m;
              m = 9 * (long) (Math.pow(10, i - 1)) * i;
          }
          //find the last num whose length is i -1
          int s = (int) (Math.pow(10, i - 1)) - 1;
          //find n can make how many num whose length is i, then add it
          s += n / i;
          //made n mod i
          n = n % i;
          //if n == 0, res is the last num in before number
          int res = s % 10;
          //else make s++, and find the nth num
          s++;
          while (n > 0) {
              res = s / (int) (Math.pow(10, i - 1)) % 10;
              i--;
              n--;
          }
          return res;
      }
      

---