Nth digit — Leetcode Problem 400

Original problem link: https://leetcode.com/problems/nth-digit/description/

In this problem, we’re asked to find the nth digit of the infinite sequence written as a string 1,2,3,4,5,6,7,8,9…

For example, the 3rd digit would be 3, but the 10th digit would be 1 (the tens place of 10) and 11th would be 0 (the ones place of 10).

Before we get to explanations, the fast approach that beats 100% of submissions is this, but we do have to use a bit of math:

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);
    }
}

Initially, it’s intuitive to use a StringBuilder to build up the sequence until we get to a length of n or greater, but that has memory limit exceeded error.

So I changed to looping through and calculating the correct number the nth digit would be from, like this:

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);
    }
}

However, this was still O(n) and would result in time limit exceeded exception. This code was useful for making sure my later calculations were correct when figuring out the math.

The way to make it faster and have it accepted was to make the solution O(log n) by finding a pattern for how many digits each number range generated, as follows

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

So now we know a formula to find what range the nth digit would fall under, but how do we find the exact number efficiently and how to find the correct digit in said number? Mathematically, it’s intuitive that it’s related to the quotient (n — numOfDigits) / power and the remainder mod = (n — numOfDigits) % power, where numOfDigits is the number of digits in the ranges before the current range (for example, for n = 83 the previous range is the 1–9 range so numOfDigits = 9). We also notice that the mod cycles within a number, with mod=0 being the last digit of a number, yielding the following (copied from the first part of this blog post):

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);
    }
}

One more note is to use longs for the calculation, otherwise it results in some very weird errors that give us very large mods and powers!