CHEFFED - Editorial

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.

7 Likes

I want to know the test cases u used for testing @Karan Aggarwal

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 :slight_smile:

2 Likes

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)?

1 Like

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?

#include

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.

2 Likes

loop runs just 90 times. So complexity is O(90) :slight_smile:

3 Likes

Corrected. Thank you

sorry yar…
i was in some trance… so, i was mistaken…

indeed it is O(1)… i.e. constant time…
what does O(90) mean??
I was just mistaken…
and someone downvoted my posts… huh…

4
999999799
999999814
999999817
999999820