Yes, you are right @tony_hager
complexity is O(90) which you can consider as constant time not O(n).
yeah… sorry… i got it wrong…
now… it’s okay…
I followed the same approach… But i got WA verdict…
#include<stdio.h>
#include<string.h>
int main()
{
char word[10];
long long int N,temp,tempcnt,cnt,i,temp2,tempcnt2,temp3;
scanf("%lld",&N);
sprintf(word,"%lld",N);
// printf("%d",strlen(word));
cnt=0;
for(i=0;i<=81;i++)
{
if(i>9)
temp2=N-(i+(i%10)+(i%100));
else
temp2=N-(i+(i%10));
// printf(" %lld",temp2);
tempcnt=0;
temp=temp2;
while(temp!=0)
{
tempcnt=tempcnt+(temp%10);
temp=temp/10;
}
temp3=tempcnt;
tempcnt2=0;
while(temp3!=0)
{
tempcnt2=tempcnt2+(temp3%10);
temp3=temp3/10;
}
// printf(" %lld",tempcnt);
if(temp2+tempcnt+tempcnt2 == N)
{
cnt++;
}
// printf("\n%lld %lld %lld %lld",cnt,temp2,tempcnt,tempcnt2); }
}
printf("%lld",cnt);
return 0;
}
where is it gone wrong??
S(S(x)) can be maximum 16, not 9!!!
Because of S(X) <= 81, but it’s also can be 79 as well.
X = 999 999 997 gives S(X)=79 gives S(S(X))=16 and S(X)+S(S(X))=95. Seems, editorialist missed this out
A simpler approach is that, Number 999999999 has the max sum of digits = 81
i.e
8 digit number has max sum of digits = 81
2 digit number has max sum of digits = 9 + 9 = 18
1 digit number has max sum of digits = 9
so 81 + 18 + 9 = 108
so checking from N = 1 to 110 would be enough.
Hello… anybody here… whose solution is accepted…??
just run for n= 999 999 894
and tell me ur count…
Hello… anybody here whose solution is accepted ??
then run your program for n = 999 999 894
and tell me your count…
kishore1 the answer for 999999894 is 4.
@code_diamond
could you put them down…
the four numbers which satisfy the equation for n = 999 999 894
S(X)+S(S(X))≤97S(X)+S(S(X))≤97 , we just need to iterate from XX = N−97N−97 to N??? but how?/
how you can find the interval of X.
CAN ANYONE PROVE IT?
In this question output of test case 999999969 is 2 in this solution CodeChef: Practical coding for everyone
while the answer should be 3.
Still got AC
What does O(97) even mean? Shouldn’t it be O(1)?
In case you write complexity like this, it sounds like you can find S(x) in O(1).
In general, why not to write it like log^2(N) or something like that?
The following C++ code when compiled gives Time limit exceeded. Can anyone help me out?
using namespace std;
int main()
{
int N,X,ctr=0,val,val2;
cin>>N;
for(X=0;X<N;X++){
int sum1=0,sum2=0,sumv=0;
val=X;
while(val!=0){
sum1=sum1+val%10;
val=val/10;
}
val2=sum1;
while(val2!=0){
sum2=sum2+val2%10;
val2=val2/10;
}
sumv=X+sum1+sum2;
if(sumv==N){
ctr++;
}
}
cout<<ctr;
return 0;
}
S(X)=79 gives S(S(X))=16 and S(X)+S(S(X))=95.
loop runs just 90 times. So complexity is O(90)
Corrected. Thank you