Nth Character in Concatenated Decimal String

Difficulty Level Medium
Frequently asked in Adobe Oracle
StringViews 2210

Problem Statement

In the “Nth Character in Concatenated Decimal String” problem we have given an integer value “n”. Write a program to find the Nth character in the string in which all decimals are concatenated.

Input Format

The first and only one line containing an integer value n.

Output Format

Print a character at position “n” in the string in which all decimals are concatenated.

Constraints

  • 1<=n<=10^5

Example

7
7

Explanation: Let’s form a string whose length is 7 and all decimals are concatenated in it. So, our string is “1234567”. Now we check the 7th character in the string which is 7. So our final answer is “7”.

10
1

Explanation: Let’s form a string in which concatenate 10 numbers. So, our string is “12345678910”. Now we check the 10th character in the string which is 1. So our final answer is “1”.

Approach

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 length 3 and so on. So skip these numbers according to the given N and find the character

1. Find the length of the number at N

2. Now, get the character at N

Example

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. So, 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

Implementation

C++ program for Nth Character in Concatenated Decimal String

#include <bits/stdc++.h> 
using namespace std; 

int main() 
{ 
  int n;
  cin>>n;
  int sum=0,nine=9,dist=0,len; 
  for(len=1; ;len++) 
  { 
    sum+=nine*len;
    dist+=nine; 
    if(sum>=n) 
    { 
      sum-=nine*len; 
      dist-=nine; 
      n-=sum; 
      break; 
    } 
    nine*=10; 
  } 
  int diff=ceil((double)n/len); 
  int d=n%len; 
  if(d==0)
  {
    d=len;
  }
  n=dist+diff;
  string str; 
  stringstream ss; 
  ss<<n; 
  ss>>str; 
  cout<<str[d - 1]<<endl; 
  return 0; 
}

Java program for Nth Character in Concatenated Decimal String

import java.util.Scanner;

class sum
{ 
  public static void main(String[] args) 
  { 
    Scanner sr = new Scanner(System.in); 
                int n=sr.nextInt();
                int sum=0,nine=9,dist=0,len;   
                for(len=1; ;len++)  
                {  
                    sum+=nine * len;  
                    dist+=nine;  
                    if(sum>=n)  
                    {   
                        sum-=nine*len;  
                        dist-=nine;  
                        n-=sum;  
                        break;  
                    }  
                    nine*=10;  
                }    
                int diff=(int)(Math.ceil((double)(n)/(double)(len)));  
                int d=n%len;  
                if(d==0)  
                {
                    d=len;
                }  
                String str=Integer.toString(dist+diff); 
                System.out.println(str.charAt(d-1)); 
  } 
} 

51
0

Complexity Analysis for Nth Character in Concatenated Decimal String

Time Complexity

O(Log N) where N is the given integer. Here the base of log is 10.

Space Complexity

O(1) because we don’t use any extra space here. We simply find the answer using a few operations using few variables.

Translate »