Digit ke-n — Masalah Leetcode 400
Tautan masalah asli:https://leetcode.com/problems/nth-digit/description/
Dalam soal ini, kita diminta mencari digit ke-n dari barisan tak terhingga yang ditulis sebagai string 1,2,3,4,5,6,7,8,9…
Misalnya, digit ke-3 adalah 3, tetapi digit ke-10 adalah 1 (tempat puluhan dari 10) dan digit ke-11 adalah 0 (tempat satuan dari 10).
Sebelum kita masuk ke penjelasan, pendekatan cepat yang mengalahkan 100% kiriman adalah ini, tetapi kita harus menggunakan sedikit matematika:
class Solution {
public int findNthDigit(int n) {
if (n < 10) {
return n;
}
long numOfDigits = 0;
long power = 1;
while (numOfDigits + (9 * (long)Math.pow(10, power - 1) * power) <= n) {
numOfDigits += (9 * (long)Math.pow(10, power - 1) * power);
power++;
}
long quotient = (n - numOfDigits) / power;
long mod = (n - numOfDigits) % power;
long i = mod == 0 ? (quotient + (long)Math.pow(10, power - 1) - 1) : (quotient + (long)Math.pow(10, power - 1));
String num = String.valueOf(i);
return mod == 0 ? Character.digit(num.charAt(num.length() - 1), 10) : Character.digit(num.charAt((int)mod - 1), 10);
}
}
Jadi saya mengubah ke perulangan dan menghitung angka yang benar dari digit ke-n, seperti ini:
class Solution {
public int findNthDigit(int n) {
int i = 0;
int prevIndex = 0;
int index = 0;
while (index < n) {
i++;
String num = String.valueOf(i);
prevIndex = index;
index += num.length();
}
String str = String.valueOf(i);
return Character.digit(str.charAt(n - prevIndex - 1), 10);
}
}
Cara membuatnya lebih cepat dan diterima adalah membuat solusi O(log n) dengan mencari pola berapa digit setiap rentang angka yang dihasilkan, sebagai berikut
Single digits 1-9 => 9 * 10^0 * 1 digits
Double digits 10-99 => 9 * 10^1 * 2 digits
...so the general formula is 9 * 10^(m - 1) * m digits for each number range
class Solution {
public int findNthDigit(int n) {
if (n < 10) {
return n;
}
long numOfDigits = 0;
long power = 1;
while (numOfDigits + (9 * (long)Math.pow(10, power - 1) * power) <= n) {
numOfDigits += (9 * (long)Math.pow(10, power - 1) * power);
power++;
}
long quotient = (n - numOfDigits) / power;
long mod = (n - numOfDigits) % power;
long i = mod == 0 ? (quotient + (long)Math.pow(10, power - 1) - 1) : (quotient + (long)Math.pow(10, power - 1));
String num = String.valueOf(i);
return mod == 0 ? Character.digit(num.charAt(num.length() - 1), 10) : Character.digit(num.charAt((int)mod - 1), 10);
}
}

![Apa itu Linked List? [Bagian 1]](https://post.nghiatu.com/assets/images/m/max/724/1*Xokk6XOjWyIGCBujkJsCzQ.jpeg)



































