0ms C++ Solution with Detail-Explanation


  • 54

    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:

    class Solution 
    {
        // date: 2016-09-18     location: Vista Del Lago III Apartments
    public:
        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;
        }
    };
    

  • 0
    S

    @Mad_air Wow!


  • 3
    K

    @Mad_air nice solution and detail explanation! Thank you!
    And pay attention to the "base" and "number" to be long int type


  • 0
    S

    Nice solution.Thanks for detail explanation!


  • 0
    F

    I have exactly the same solution / ideas as you do. I am thinking about if this is the only way to solve this problem?


  • 2
    F

    @Mad_air I believe there is an overflow bug in this solution. Try n = 1000000000.


  • 0

    The thought is easy. But it is not easy to implement it correctly.
    Nice work!


  • 0
    L

    @Mad_air Thks for the detail explanation. It's very clear!


  • 0
    S
    This post is deleted!

  • 0
    S

    @fasdafe Indeed.
    This is my modified version using the same idea.

    class Solution {
    public:
    // 9 (1-digit-num)-> 90 (2-digit-num) -> 900 -> 9000
    int findNthDigit(int n) {

        long long int sectionElements = 0;
        long long int numDigits = 0;
        long long int leftDigits = n;
        
        long long int lastLeftDigits = n;
        int cumElements = 0;
        
        while(leftDigits > 0){
            lastLeftDigits = leftDigits;
            cumElements += sectionElements;
        
            numDigits ++;
            sectionElements = sectionElements == 0 ? 9 : sectionElements*= 10;
            leftDigits -= sectionElements*numDigits;
            
            //cout << leftDigits << endl;
        }
        
        //cout << lastLeftDigits << "\t" << numDigits << endl;
        
        // 7 -> lastLeftDigits = 7, numDigits = 1
        // 11 -> lastLeftDigits = 2, numDigits = 2
        // 190 -> lastLeftDigits = 2, numDigits = 3
        // 1000000000 (potentially overflow case)
        int elementPos = (lastLeftDigits-1)/(numDigits);
        int offset = (lastLeftDigits-1)%numDigits;
        elementPos += 1;
        offset = numDigits-1-offset;
        
        int targetNum = cumElements + elementPos;
        
        return (int)(targetNum/pow((int)10,(int)offset))%10;  
    }
    

    };


  • 0

    Same idea. C# code,

    using System;
    using System.Linq;
    using System.Collections.Generic;
    using System.Text;
    
    public class Solution
    {
        public int FindNthDigit(int n)
        {
            int digitCount = 1;
            int previousMaxInRange = 0;
            int maxInRange = 0;
    
            // find the length of numbers that nth digit comes from
            for (digitCount = 1; digitCount <= 10; digitCount++)
            {
                previousMaxInRange = maxInRange;
                maxInRange += 9 * (int)Math.Pow(10, digitCount - 1) * digitCount;
    
                if (n <= maxInRange || maxInRange < previousMaxInRange || maxInRange < 0)
                {
                    break;
                }
            }
    
            // find the number.
            int diff = n - previousMaxInRange;
            int number = (int)(Math.Pow(10, digitCount-1) - 1) + diff / digitCount;
            number = (diff % digitCount != 0) ? number + 1 : number;
    
            int denominator = (diff % digitCount != 0) ? (int)(Math.Pow(10, digitCount - (diff % digitCount))) : 1;
    
            // calculate the result
            return (number / denominator) % 10;
        }
    }
    

  • 0
    H

    @fasdafe There is no overflow bug, because the condition in the while statement has prevent this.


  • 0

    @fasdafe could you please explain why there is an overflow error? In my code there is a wrong answer which outputs 8 not 1.


  • 0
    J

    @yong.cao.7731 I cannot agree more. I figured out this method quite easily. But, spent 25 mins on debugging...


  • 0
    C

    Well, my solution has the same idea, but it just won't pass the test cases because of running time exceeded. I just don't understand what's the difference.

    class Solution {
    public:
    	int findNthDigit(int n) {
    		int sum = 0;
    		int c = 1;            //  digits
    		while (sum < n) {
    			sum += 9 * pow(10, c - 1) * c;
    			c++;
    		}
    		c--;
    		sum -= 9 * pow(10, c - 1) * c;
    		int num = ceil((double)(n - sum) / c + pow(10, c - 1) - 1);
    		int position = (n - sum) % c;       //   index
    		string str = to_string(num);
    		return position == 0 ? str[str.size() - 1] - '0' : str[position - 1] - '0';
    	}
    };
    

  • 1
    L

    @Caramel overflow of variable sum? Try long long sum = 0.


  • 0
    C

    @ltong2016 Thanks a lot! I neglected it before. Now the problem is perfectly solved.


  • 0
    L

    Great explanation, but I did not get it at the first glance of your code, I think coding this according to what you have explained is much more easier to understand, take a look at my code, no fancy if -- else, just simple plain code.

    class Solution 
    {
    public:
        int findNthDigit(int n) 
        {
            if(n <= 9)
            {
                return n;
            }
    
            long base = 9, digits = 1;
            long range_start = 1;
            long range_end = 9;
            while (n - base * digits > 0)
            {
                range_start *= 10;
                range_end *= 10;
                n -= base * digits;
                base *= 10;
                digits ++;
            }
    
            long expected_num = range_start + (n  - 1) / digits;
    
            vector<int> vec;
            while(expected_num)
            {
                vec.push_back(expected_num % 10);
                expected_num /= 10;
            }
            
            reverse(vec.begin(), vec.end());
            
            return vec[(n - 1) % digits];
        }
    };
    

Log in to reply
 

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