Home » Interview Questions » String Interview Questions » Nth character in Concatenated Decimal string

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

READ  String comparison containing wildcards

 

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions