Given an integer N, the task is to find the N-th character in the string made by concatenating natural numbers (Integers beginning from 1). The starting string will be “12345678910111213..”.
Examples:
Input: N = 3 Output: 3 3rd character in the string "12345678910111213.." is 3. Input: N = 11 Output: 0 11th character in the string "12345678910111213..." is 0
The idea is to generate the required string until string length does exceed N.
- Initialize a Null string and c=1
- Add the c to the string by type-casting it to a character
- If c is a single-digit number, append it to the string
- if c is greater than 9, then store it in a temporary string and reverse it and append to the original string
- If at any moment the string length exceeds N, then return s[n-1].
Below is the implementation of the above approach:
C++
// C++ program to find the N-th character// in the string "1234567891011.."#include <bits/stdc++.h>using namespace std;// Function that returns the N-th characterchar NthCharacter(int n){ // initially null string string s = ""; // starting integer int c = 1; // add integers in string for (int i = 1;; i++) { // one digit numbers added if (c < 10) s += char(48 + c); // more than 1 digit number, generate // equivalent number in a string s1 // and concatenate s1 into s. else { string s1 = ""; int dup = c; // add the number in string while (dup) { s1 += char((dup % 10) + 48); dup /= 10; } // reverse the string reverse(s1.begin(), s1.end()); // attach the number s += s1; } c++; // if the length exceeds N if (s.length() >= n) { return s[n - 1]; } }}// Driver Codeint main(){ int n = 11; cout << NthCharacter(n); return 0;} |
Java
// Java program to find the N-th character// in the string "1234567891011.."class GFG{ // Function that returns the N-th character static char NthCharacter(int n) { // initially null string String s = ""; // starting integer int c = 1; // add integers in string for (int i = 1;; i++) { // one digit numbers added if (c < 10) s += Integer.toString(c); // more than 1 digit number, generate // equivalent number in a string s1 // and concatenate s1 into s. else { String s1 = ""; int dup = c; // add the number in string while (dup >0) { s1 += Integer.toString(dup % 10); dup /= 10; } // reverse the string StringBuilder temp = new StringBuilder(); temp.append(s1); temp = temp.reverse(); // attach the number s += temp; } c++; // if the length exceeds N if (s.length() >= n) { return s.charAt(n - 1); } } } // Driver Code public static void main(String []args) { int n = 11; System.out.println( NthCharacter(n)); }}// This article is contributed by ihritik |
Python3
# Python 3 program to find the N-th character# in the string "1234567891011.."# Function that returns the N-th characterdef NthCharacter(n): # initially null string s = "" # starting integer c = 1 # add integers in string while(True) : # one digit numbers added if (c < 10): s += chr(48 + c) # more than 1 digit number, generate # equivalent number in a string s1 # and concatenate s1 into s. else: s1 = "" dup = c # add the number in string while (dup > 0): s1 += chr((dup % 10) + 48) dup //= 10 # reverse the string s1 = "".join(reversed(s1)) # attach the number s += s1 c += 1 # if the length exceeds N if (len(s) >= n): return s[n - 1]# Driver Codeif __name__ == "__main__": n = 11 print(NthCharacter(n))# This code is contributed by ita_c |
C#
// C# program to find the N-th character// in the string "1234567891011.." using System;class GFG{ // Function that returns the N-th character static char NthCharacter(int n) { // initially null string String s = ""; // starting integer int c = 1; // add integers in string for (int i = 1;; i++) { // one digit numbers added if (c < 10) s += c.ToString(); // more than 1 digit number, generate // equivalent number in a string s1 // and concatenate s1 into s. else { String s1 = ""; int dup = c; // add the number in string while (dup > 0) { s1 += (dup % 10).ToString(); dup /= 10; } // reverse the string String temp = reverse(s1); // attach the number s += temp; } c++; // if the length exceeds N if (s.Length >= n) { return s[n - 1]; } } } static String reverse(String input) { char[] a = input.ToCharArray(); int l, r = 0; r = a.Length - 1; for (l = 0; l < r; l++, r--) { // Swap values of l and r char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.Join("", a); } // Driver Code public static void Main(String []args) { int n = 11; Console.WriteLine( NthCharacter(n)); }}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript program to find the N-th character// in the string "1234567891011.."// Function that returns the N-th characterfunction NthCharacter(n){ // initially null string let s = ""; // starting integer let c = 1; // add integers in string for (let i = 1;; i++) { // one digit numbers added if (c < 10) s += c.toString(); // more than 1 digit number, generate // equivalent number in a string s1 // and concatenate s1 into s. else { let s1 = ""; let dup = c; // add the number in string while (dup >0) { s1 += (dup % 10).toString(); dup = Math.floor(dup/10); } // reverse the string s1=s1.split("").reverse().join(""); // attach the number s += s1; } c++; // if the length exceeds N if (s.length >= n) { return s[n-1]; } }}// Driver Codelet n = 11;document.write( NthCharacter(n)); // This code is contributed by avanitrachhadiya2155</script> |
Output
0
Complexity Analysis:
- Time Complexity: O(N2), as we are traversing N times using a loop and in each traversal we are using reverse function which will cost O (N), so in the worst case the program will effectively cost O (N*N).
- Auxiliary Space: O(N), as we are using extra space for the string.
New Approach:-
- Calculate the length of the number where the N-th character is present and store it in variable “length”.
- Find the actual number where the N-th character is present and store it in variable “number”.
- Calculate the position of the N-th character in the “number” and store it in variable “position”.
- Return the character at the “position” in the “number”.
Below is the implementation of the above approach :
C++
// C++ code to find the N-th character in the concatenated string of numbers#include <bits/stdc++.h>using namespace std;// Function that returns the N-th characterchar NthCharacter(int n) { int length = 0; int number = 1; // loop until the length of the concatenated string is less than or equal to n while (length < n) { // calculate the length of the current number int currentLength = (int) log10(number) + 1; // if the concatenated length + current length is greater than or equal to n, break the loop if (length + currentLength >= n) { break; } // add the current length to the concatenated length length += currentLength; // move to the next number number++; } // calculate the position of the N-th character in the number int position = n - length - 1; // convert the number to a string string numStr = to_string(number); // return the N-th character return numStr[position];}// Driver Codeint main() { int n = 11; cout << NthCharacter(n) << endl; return 0;} |
Python3
# Python code to find the N-th character# in the concatenated string of numbersimport math# Function that returns the N-th characterdef NthCharacter(n): length = 0 number = 1 # loop until the length of the concatenated # string is less than or equal to n while length < n: # calculate the length of the current number currentLength = int(math.log10(number)) + 1 # if the concatenated length + current # length is greater than or equal to # n, break the loop if length + currentLength >= n: break # add the current length to the # concatenated length length += currentLength # move to the next number number += 1 # calculate the position of the N-th # character in the number position = n - length - 1 # convert the number to a string numStr = str(number) # return the N-th character return numStr[position]# Driver Codeif __name__ == '__main__': n = 11 print(NthCharacter(n)) |
Java
class GFG { // Function that returns the N-th character static char NthCharacter(int n) { int length = 0; int number = 1; // loop until the length of the concatenated string is less than or equal to n while (length < n) { // calculate the length of the current number int currentLength = (int) Math.log10(number) + 1; // if the concatenated length + current length is greater than or equal to n, break the loop if (length + currentLength >= n) { break; } // add the current length to the concatenated length length += currentLength; // move to the next number number++; } // calculate the position of the N-th character in the number int position = n - length - 1; // convert the number to a string String numStr = Integer.toString(number); // return the N-th character return numStr.charAt(position); } // Driver Code public static void main(String []args) { int n = 11; System.out.println(NthCharacter(n)); }} |
C#
// C# code to find the N-th character// in the concatenated string of numbersusing System;class Program { // Function that returns the N-th character static char NthCharacter(int n) { int length = 0; int number = 1; // loop until the length of the // concatenated string is less than // or equal to n while (length < n) { // calculate the length of // the current number int currentLength = (int)Math.Log10(number) + 1; // if the concatenated length + current // length is greater than or equal // to n, break the loop if (length + currentLength >= n) { break; } // add the current length to the // concatenated length length += currentLength; // move to the next number number++; } // calculate the position of the // N-th character in the number int position = n - length - 1; // convert the number to a string string numStr = number.ToString(); // return the N-th character return numStr[position]; } // Driver Code static void Main(string[] args) { int n = 11; Console.WriteLine(NthCharacter(n)); }} |
Javascript
// Function that returns the N-th characterfunction NthCharacter(n) { let length = 0; let number = 1; // loop until the length of the concatenated string is less than or equal to n while (length < n) { // calculate the length of the current number let currentLength = Math.floor(Math.log10(number)) + 1; // if the concatenated length + current length is greater than or equal to n, break the loop if (length + currentLength >= n) { break; } // add the current length to the concatenated length length += currentLength; // move to the next number number++; } // calculate the position of the N-th character in the number let position = n - length - 1; // convert the number to a string let numStr = number.toString(); // return the N-th character return numStr[position];}// Driver Codelet n = 11;console.log(NthCharacter(n)); |
Output
0
Time Complexity:- The time complexity of the given code is O(log n) because the loop iterates until the length of the concatenated string is less than or equal to n. The number of iterations in the loop is proportional to the logarithm of n.
Auxiliary Space:- The auxiliary space complexity of the code is O(1) because it uses a constant amount of extra space regardless of the input size. The variables used in the code are of fixed size, and no extra space is allocated dynamically. Therefore, the space used by the code remains constant.
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!
