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 codepublic 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 Ndef getDigit(N, d): string = str(N) return string[d-1]; # Method to return Nth character in concatenated# decimal stringdef 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 methodsN = 251print (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 codestatic 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 Nfunction getDigit($N, $d){ $string = strval($N); return $string[$d - 1];}// Method to return Nth character // in concatenated decimal stringfunction 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 Codelet 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.
If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
