Java solution


  • 146
    L

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

  • 11

    I got the same idea as you, while making the solution a mess...

    Great implementation!


  • 1
    B

    Same Idea. Here is my code:

    public int findNthDigit(int n) {
            int sub = 9, bit = 1;
            while((long)n > (long)sub*bit){
                n -= sub*bit;
                sub *= 10;
                bit++;
            }
            int a = (int)Math.pow(10, bit-1) + (n-1) / bit;
            int b = (n-1) % bit;
            return Character.getNumericValue(String.valueOf(a).charAt(b));
        }

  • 1
    F

    Same idea C++:

    class Solution {
    public:
        int findNthDigit(int n) {
            int d = 1;
            long acc = 9;
            int i = 1;
            
            while(n > d*acc){
                n-=(d++)*acc;
                i+=acc;
                acc*=10;
            }
    
            return to_string(i+(n-1)/d)[(n-1)%d] - '0';
        }
    
    
    };

  • 3
    B

    I think my solution may be a little faster since I pre-stored a digit-number mapping:

        public int findNthDigit(int n) {
            int[] digitInd = {1, 10, 190, 2_890, 38_890, 488_890, 5_888_890, 68_888_890, 788_888_890};
            int[] nums     = {1, 10, 100, 1_000, 10_000, 100_000, 1_000_000, 10_000_000, 100_000_000};
            int i;
            for (i = 0; i < digitInd.length - 1 && digitInd[i + 1] <= n; i++);
            int digitNum = i + 1;
            int offset = n - digitInd[i];
            int num = nums[i] + offset / digitNum;
            offset %= digitNum;
            for (n = digitNum - offset - 1; n > 0; n--, num /= 10);
            return num % 10;
        }
    

  • 4
    I

    @lzb700m Nice use of toString, I used math instead, which is theoretically more efficient. ^___^

            int len = 1, base = 1;
            for (; n > 9L * base * len; base *= 10) {
                n -= 9 * base * len;
                len++;
            }
            int ans = 0, num = (n - 1)/len + base;
            for (int i = (n - 1) % len; i < len; ++i) {
                ans = num % 10;
                num /= 10;
            }
            return ans;
    

  • 1
    E

    there is an interesting approach. get summation of upto digits i . we no need to go for a loop. it is simple observation
    1= 9
    2=> 189 (9+ 90 *2)
    3 =>2889(9 + 180+ 900 *3)
    so pattern is for ith digits Summation Σi = (i-1) 8 appears (i-1) times followed by 9
    here first digit is i-1, last digit is 9 and in-between there are i-1 8s.
    4==> 3 888 9=38889
    8==> 788888889

    	Approach is :: get the length-1 of the number ,get the summation subtract input number with this to get a number which will be divided by length of the current number length
    	for example: 4000 is input.
    	 so get the summation of 3(length-1) which is 2 88 9. 4000-2889 = 1111 
    	 999 + 1111/4 = 266 ,with remainder 3. so  third digit of 277 which is 7 is the answer

  • 1
    Y

    same idea in C++

    class Solution {
    public:
      int findNthDigit(int n) {
        int len = 1, base = 1;
        while (n > 9L * base * len) {
          n -= 9 * base * len;
          len++;
          base *= 10;
        }
        int start = (n-1)/len + base, remain = (n-1)%len;
        while (remain--)
          base /= 10;
        return (start/base)%10;
      }
    };
    

  • 2
    S

    start += (n - 1) / len;

    Can someone explain why we subtract 1 here? Trying to wrap my head around the logic.


  • 4

    @sean46 Because, n in that situation is the relative number of the digit beginning from start and so on. In that case len is how much digits the numbers where the digit we are searching for have. So, we want to know the exact number where the digits is. If n is multiple of len then you will get a number one bigger than the original number. I guess that is the answer, or at least I understand it like this.


  • 0
    J
    This post is deleted!

  • 0
    A
    This post is deleted!

  • 0
    K

    Here's how I pre-calculated the mapping:

    import java.util.ArrayList;
    import java.util.List;
    
    public class Solution {
        private static final List<Integer> scale = new ArrayList<>();
        
        static {
            int len = 1;
            int count = 9;
            int total = 9;
            scale.add(1);
            
            // Init scale
            while (total > scale.get(scale.size() - 1)) {
                scale.add(total+1);
                count *= 10;
                len++;
                total = total + count*len;
            }
        }
        
        public int findNthDigit(int n) {
            // Choose scale
            int i = scale.size() - 1;
            while (i > 0) {
                if (scale.get(i) < n)
                    break;
                i--;
            }
            int len = i+1;
            int start = scale.get(i);
            int number = (int)Math.pow(10, len - 1) + (n - start)/len;
            return Character.getNumericValue(String.valueOf(number).charAt((n - start)%len));
        }
    }
    

  • 0
    C

    amazing approach. I was having hard time to figure out how to find the number to which input belongs. your solution made it easier!


  • 3

    @sean46 said in Java solution:

    start += (n - 1) / len;

    Can someone explain why we subtract 1 here? Trying to wrap my head around the logic.

    The reason why (n-1) is to keep the correct digits finally in number they correspond to. Eg: if we are trying to find the 192th digit, we know range from 1th digit to 9th digit belongs to numbers from 1 to 9 and range from 10th to 189th belongs to numbers from 10 to 99, right? So it is obvious that the next number should be 100 and the 192th digit should be the 3rd digit of 100(now n=3). OK, back to the code, if we donot minus 1 from n and then devide the len, the 192th digit would go to the next number which is 101.


  • 1

    How to figure out the time complexity of the code?


  • 3

    @OpMaker

    This likely is a O(logN) algorithm.
    The while loop has lgN iterations at most, since count is multiplied by 10 in each loop.
    The time complexity of .toString() is dictated by the length of start, which is also decided by the while loop, and as such it's lgN.


  • 0

    @zzhai Thanks! It makes sense.


  • 0
    H

    Just don't understand why the type of count should be 'long' instead of 'int'?


  • 2

    @Henry456 said in Java solution:

    Just don't understand why the type of count should be 'long' instead of 'int'?

    Because of overflow.

    Let's say we use int instead of long.

    int count can take 2,147,483,647 maximally.
    When you do count = 9 * 109, which is 9,000,000,000, int count overflowed.
    It will be considered as a small positive number, instead of the large positive number you intend to have.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.