CHEFFED - Editorial

PROBLEM LINK:

Practice
Contest

Author: Misha Chorniy
Tester: Karan Aggarwal
Editorialist: Pushkar Mishra

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

Given a number N, find the number of integers X such that X + S(X) + S(S(X)) = N. Here, S(k) denotes sum of digits of integer K.

EXPLANATION:

The first thing to note is that no number strictly greater than N can satisfy the equation. So we only care about numbers less than or equal to N.
The next thing to note is that we are given the constraint that N \leq 10^9. This means S(X) can at maximum be 81 for any X \leq N. This is because the largest number below 10^9 is 999999999 whose digits add up to 81. The digits of 10^9 add up to 1 anyway. So, S(X) \leq 81, and we have that S(S(X)) \leq 16 (maximum case is for 79). Summing the two inequalities, we have that S(X) + S(S(X)) \leq 97.

This gives us an efficient algorithm to calculate the number of integers that satisfy the equation. Since, S(X) + S(S(X)) \leq 97, we just need to iterate from X = N-97 to N and check which integers satisfy the equation because no integer smaller than N-97 can satisfy the equation and neither can any integer greater than N.

Please see editorialist’s/setter’s program for implementation details.

COMPLEXITY:

\mathcal{O}(97)

SAMPLE SOLUTIONS:

Author
Tester
Editorialist
Admin

4 Likes

You are iterating from n-90 to n…
so, the complexity is O(n)…
kindly check it…

Yes, you are right @tony_hager

complexity is O(90) which you can consider as constant time not O(n).

3 Likes

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.

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