Nth character in Concatenated Decimal string

Given a string in which all decimals are concatenated , write a function to find the Nth character in the string.

Example

INPUT
s = "123456789101112131415....."

OUTPUT
For N = 7, OUTPUT : 7
For N= 10, OUTPUT : 1
For N = 51, OUTPUT : 0

In this method the main idea is, considering the fact that in decimal 9 numbers are of length 1, 90 numbers are of length 2 and 900 numbers are of lengthh 3 and so on. So skip these numbers according to the given N and find the charcater

Algorithm

1. Find the length of the number at N

2. Now, get the character at N

Implementation of above algorithm

Example,

INPUT : N = 51

1) Finding the length of the number at N
    51 - 9 = 42 // There are 9 numbers with length 1
    42 - 90*2 < 0 // As there are 90 numbers with length 2, we got to know that the length is 2

2) Find the character at N
    42 characters are after max 1 digit number(ie, 9)
    ceil(42/2) = 21,so  9+21 = 30
    30 is the number at N
    Now, finding the actual character at N
    42%2 = 0, so take 2nd digit of 30

Therefore, 0 is the character at N

C++ Program

#include <bits/stdc++.h>
using namespace std;
 
//  To find the digit at N
char findDigit(int N, int d)
{
    string s;
    stringstream ss;
    ss << N;
    ss >> s;
    return s[d - 1];
}
 
// Method to return Nth character in concatenated
// decimal string
char getNthChar(int N)
{
    //  no_of_chars will store character escaped till now
    int no_of_chars = 0, nine = 9;
 
    //  no_of_nums will store numbers escaped till now
    int no_of_nums = 0, len;
 
    //  loop for number lengths
    for (len = 1; ; len++)
    {
        // increament with nine*len chars
        no_of_chars += nine*len;
        //increment with nine numbers
        no_of_nums += nine;
 
        if (no_of_chars >= N)
        {
            //  restore variables to previous correct state
            no_of_chars -= nine*len;
            no_of_nums -= nine;
            N -= no_of_chars;
            break;
        }
        nine *= 10;
    }
 
    // differnce fomr las max digit
    int diff = ceil((double)N / len);
 
    // d will store dth digit of current number
    int d = N % len;
    cout<<d<<endl;
    if (d == 0)
        d = len;
    cout<<d;
 
    // method will return the digit at N
    return getDigit(no_of_nums + diff, d);
}


int main()
{
    int N = 51;
    cout << getNthChar(N) << endl;
    return 0;
}
Try It

 


Next > < Prev
Scroll to Top