CHEFFED - Editorial

editorial
, , ,
1

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

2 Likes
2

S(X)=79 gives S(S(X))=16 and S(X)+S(S(X))=95.

2 Likes
3

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

4

Yes, you are right @tony_hager

5

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

3 Likes
6

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

2 Likes
7

yeah… sorry… i got it wrong…
now… it’s okay…

8

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

9

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
10

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

11

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
12

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.

13

Corrected. Thank you

14

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

15

Hello… anybody here… whose solution is accepted…??
just run for n= 999 999 894
and tell me ur count…

16

Hello… anybody here whose solution is accepted ??
then run your program for n = 999 999 894
and tell me your count…

17

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

18

kishore1 the answer for 999999894 is 4.

19

@code_diamond
could you put them down…
the four numbers which satisfy the equation for n = 999 999 894

20

4
999999799
999999814
999999817
999999820