Nth character in Concatenated Decimal String
If all decimal numbers are concatenated in a string then we will get a string that looks like string P as shown below. We need to tell the Nth character of this string.
P = “12345678910111213141516171819202122232425262728293031….”
Examples:
N = 10 10th character is 1 N = 11 11th character is 0 N = 50 50th character is 3 N = 190 190th character is 1
We can solve this problem by breaking the string length-wise. We know that in decimal 9 numbers are of length 1, 90 numbers are of length 2, 900 numbers are of length 3 and so on, so we can skip these numbers according to the given N and can get the desired character.
Processing for N = 190 is explained below, P[184..195] = “979899100101” First getting length of number at N, 190 – 9 = 181 number length is more than 1 181 – 90*2 = 1 number length is more than 2 1 – 900*3 < 0 number length is 3 Now getting actual character at N, 1 character after maximum 2 length number(99) is, 1 Processing for N = 251 is explained below, P[250..255] = “120121” First getting length of number at N, 251 - 9 = 242 number length is more than 1 242 – 90*2 = 62 number length is more than 2 62 – 900*3 < 0 number length is 3 Now getting actual character at N, 62 characters after maximum 2 length number(99) is, Ceil(62/3) = 21, 99 + 21 = 120 120 is the number at N, now getting actual digit, 62%3 = 2, 2nd digit of 120 is 2, so our answer will be 2 only.
Implementation:
C++
// C++ program to get Nth character in // concatenated Decimal String #include <bits/stdc++.h> using namespace std; // Utility method to get dth digit of number N char getDigit( int N, int d) { string str; stringstream ss; ss << N; ss >> str; return str[d - 1]; } // Method to return Nth character in concatenated // decimal string char getNthChar( int N) { // sum will store character escaped till now int sum = 0, nine = 9; // dist will store numbers escaped till now int dist = 0, len; // loop for number lengths for (len = 1; ; len++) { // nine*len will be incremented characters // and nine will be incremented numbers sum += nine*len; dist += nine; if (sum >= N) { // restore variables to previous correct state sum -= nine*len; dist -= nine; N -= sum; break ; } nine *= 10; } // get distance from last one digit less maximum // number int diff = ceil (( double )N / len); // d will store dth digit of current number int d = N % len; if (d == 0) d = len; // method will return dth numbered digit // of (dist + diff) number return getDigit(dist + diff, d); } // Driver code to test above methods int main() { int N = 251; cout << getNthChar(N) << endl; return 0; } |
Java
// Java program to get Nth character in // concatenated Decimal String class GFG { // Utility method to get dth digit of number N static char getDigit( int N, int d) { String str=Integer.toString(N); return str.charAt(d - 1 ); } // Method to return Nth character in concatenated // decimal string static char getNthChar( int N) { // sum will store character escaped till now int sum = 0 , nine = 9 ; // dist will store numbers escaped till now int dist = 0 , len; // loop for number lengths for (len = 1 ; ; len++) { // nine*len will be incremented characters // and nine will be incremented numbers sum += nine * len; dist += nine; if (sum >= N) { // restore variables to previous correct state sum -= nine * len; dist -= nine; N -= sum; break ; } nine *= 10 ; } // get distance from last one digit // less maximum number int diff = ( int )(Math.ceil(( double )(N) / ( double )(len))); // d will store dth digit of current number int d = N % len; if (d == 0 ) d = len; // method will return dth numbered digit // of (dist + diff) number return getDigit(dist + diff, d); } // Driver code public static void main (String[] args) { int N = 251 ; System.out.println(getNthChar(N)); } } // This code is contributed by mits |
Python3
# Python program to get Nth character in # concatenated Decimal String # Method to get dth digit of number N def getDigit(N, d): string = str (N) return string[d - 1 ]; # Method to return Nth character in concatenated # decimal string def getNthChar(N): # sum will store character escaped till now sum = 0 nine = 9 # dist will store numbers escaped till now dist = 0 # loop for number lengths for len in range ( 1 ,N): # nine*len will be incremented characters # and nine will be incremented numbers sum + = nine * len dist + = nine if ( sum > = N): # restore variables to previous correct state sum - = nine * len dist - = nine N - = sum break nine * = 10 # get distance from last one digit less maximum # number diff = (N / / len ) + 1 # d will store dth digit of current number d = N % len if (d = = 0 ): d = len # method will return dth numbered digit # of (dist + diff) number return getDigit(dist + diff, d); # Driver code to test above methods N = 251 print (getNthChar(N)) # Contributed by Afzal_Saan |
C#
// C# program to get Nth character in // concatenated Decimal String using System; class GFG { // Utility method to get dth digit of number N static char getDigit( int N, int d) { string str = Convert.ToString(N); return str[d - 1]; } // Method to return Nth character in // concatenated decimal string static char getNthChar( int N) { // sum will store character // escaped till now int sum = 0, nine = 9; // dist will store numbers // escaped till now int dist = 0, len; // loop for number lengths for (len = 1; ; len++) { // nine*len will be incremented characters // and nine will be incremented numbers sum += nine * len; dist += nine; if (sum >= N) { // restore variables to previous // correct state sum -= nine * len; dist -= nine; N -= sum; break ; } nine *= 10; } // get distance from last one digit // less maximum number int diff = ( int )(Math.Ceiling(( double )(N) / ( double )(len))); // d will store dth digit of // current number int d = N % len; if (d == 0) d = len; // method will return dth numbered // digit of (dist + diff) number return getDigit(dist + diff, d); } // Driver code static void Main() { int N = 251; Console.WriteLine(getNthChar(N)); } } // This code is contributed by mits |
PHP
<?php // PHP program to get Nth character // in concatenated Decimal String // Method to get dth digit // of number N function getDigit( $N , $d ) { $string = strval ( $N ); return $string [ $d - 1]; } // Method to return Nth character // in concatenated decimal string function getNthChar( $N ) { // sum will store character // escaped till now $sum = 0; $nine = 9; // dist will store numbers // escaped till now $dist = 0; // loop for number lengths for ( $len = 1; $len < $N ; $len ++) { // nine*len will be incremented characters // and nine will be incremented numbers $sum += $nine * $len ; $dist += $nine ; if ( $sum >= $N ) { // restore variables to // previous correct state $sum -= $nine * $len ; $dist -= $nine ; $N -= $sum ; break ; } $nine *= 10; } // get distance from last one // digit less maximum number $diff = ( $N / $len ) + 1; // d will store dth digit // of current number $d = $N % $len ; if ( $d == 0) $d = $len ; // method will return dth numbered // digit of (dist + diff) number return getDigit( $dist + $diff , $d ); } // Driver code $N = 251; echo getNthChar( $N ); // This code is contributed by mits ?> |
Javascript
<script> // JavaScript program to get Nth // character in concatenated // Decimal String // Utility method to get dth // digit of number N function getDigit(N, d) { let str = N.toString(); return str[d - 1]; } // Method to return Nth character in // concatenated decimal string function getNthChar(N) { // Sum will store character // escaped till now let sum = 0, nine = 9; // dist will store numbers // escaped till now let dist = 0, len; // Loop for number lengths for (len = 1; ; len++) { // nine*len will be incremented // characters and nine will be // incremented numbers sum += nine * len; dist += nine; if (sum >= N) { // Restore variables to // previous correct state sum -= nine * len; dist -= nine; N -= sum; break ; } nine *= 10; } // Get distance from last one digit // less maximum number let diff = (Math.ceil((N) / (len))); // d will store dth digit // of current number let d = N % len; if (d == 0) d = len; // Method will return dth numbered digit // of (dist + diff) number return getDigit(dist + diff, d); } // Driver Code let N = 251; document.write(getNthChar(N)); // This code is contributed by code_hunt </script> |
Output
2
Time Complexity: O(Log N), where N is the given integer.
Auxiliary Space: O(1), since no extra Space used.
Contact Us