How to reduce time complexity!

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

int main()
{
//write your code here
int t,n,a;
cin>>t;
while(t>0)
{
int c=0;
cin>>n;
for(int i=1;i<n;i++)
{
int f=i;
while(f!=0)
{
a=f%10;
c++;
f=f/10;
}
}
cout<<c+2<<endl;
t–;
}
return 0;
}

Please either format your code or link to your submission - the forum software has mangled it and it won’t compile! :slight_smile:

Also - what Problem are you trying to solve?

1 Like

2 Likes

Actually the algorithm you chose is extremely inefficient for this task. One thing you should remember is your computer can do 10^9 tasks per sec, so you need to devise an algorithm with running time < O(10^9). Yours is way beyond that.
One better algorithm to use is:

-> Let the total digits of n(input) be k, lets say n is 15763 hence k is 5.
->Upto k-1 add loop sum+=9xpow(10,i)xi. for above example 9x1+90x2+900x3+9000x4.
->add sum+=(n-pow(10,k))xk in the end. i.e sum+=(15763-10000)x5.
You’re done. This is a lot more efficient

2 Likes

USE DP
Logic :
Let DP[i] be the total number of digits required to number all numbers having digits (1 , 2, 3, …i)
ie.
DP[1] = 9 , to represent all numbers till 9
DP[2] = 189 = 180 + 9 = 180+DP[1] ,to represent all numbers till 99 , 9 one digit + 90 * 2 digit nos.
DP[3] = 2889 = 900*3 + DP[2]
DP[i] = 9 x pow(10,i-1) x i + DP[i-1]

Now for some number x , having d digits, the required ans is to represent all numbers of d-1 digts and then numbers of d digits till x
ie. DP[d-1] + ( x-pow(10,d-1)+1 numbers ) X d digits

Code :
#include<bits/stdc++.h>
#define lli long long int
using namespace std;
lli DP[10]; // dp[i] = digits req to label all numbers till biggest number of i digits

int digits(lli d)
{
if(d==0) return 1;
int c = 0;
while(d!=0)
{
d/=10;
++c;
}
return c;
}

int dp(int d)
{
if(d==0) return 0;
if(DP[d]==0)
DP[d] = d9(pow(10,d-1)) + dp(d-1);
return DP[d];
}
int main()
{
for(int i=0;i<10;++i) DP[i] = 0;
int t;
cin>>t;
while(t–)
{
lli n;
cin>>n;
int d = digits(n);
lli ans = dp(d-1) + d*(n-pow(10,d-1)+1);
cout<<ans<<endl;
}
return 0;
}