Problem Link:

https://www.codechef.com/COHA2019/problems/RHSAT

Setter: ankit_singhal

Tester: anshu_7

Editorialist: anshu_7

DIFFICULTY:

Easy

PREREQUISITES:

Strings, greedy, Brute Force

Problem:

Guruji wants to explain the rahasya of satyug project to Gaitonde. But to understand this project Gaitonde needs to solve a problem. The problem describes there are q queries each query contains integer n. String s should be obtained by appending each integer 1 to n . (if n=10 ,then s=12345678910) . Gaitonde have to find the sum of nth digit of string s in each queries. Since Gaitonde is not good at problem-solving. So he gave you to solve this problem for him.

Explanation:

First we check maximum n over all queries and store each query in an array. Then we append all the numbers up to maximum n in a string (if max n=11 , then s=1234567891011) . Finally, we iterate to all queries and get the required sum by adding the nth digit (in each query) of that string.

If q = 4

[2, 7, 11, 10]

Then

S= 1234567891011

sum= 2 + 7 + 0 + 1 = 10

Time Complexity:

O(q+max(n))

Setter Solution:

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

int main()

{

ll q,ans=0,check_max=0,i=0;

cin>>q;

ll arr[q];

```
while(i<q)
{
ll n;
cin>>n;
arr[i]=n;
check_max=max(check_max,n);
i++;
}
string s="";
for(ll j=1;j<=check_max;j++)
s+=to_string(j);
for(ll j=0;j<q;j++)ans+=s[arr[j]-1]-'0';
cout<<ans;
```

}