×

# CHEFFED - Editorial

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

Easy

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:

This question is marked "community wiki".

1.3k156581
accept rate: 4%

3

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

(25 Jul '16, 00:13)

 13 S(S(x)) can be maximum 16, not 9!!! Because of S(X) <= 81, but it's also can be 79 as well. answered 25 Jul '16, 00:33 71●2 accept rate: 0% Corrected. Thank you (25 Jul '16, 00:55)
 4 complexity is O(90) which you can consider as constant time not O(n). answered 25 Jul '16, 00:25 304●9 accept rate: 10%
 4 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 :) answered 25 Jul '16, 00:38 4★lohit_97 342●8 accept rate: 4%
 2 What does O(97) even mean? Shouldn't it be O(1)? answered 28 Jul '16, 18:19 2.4k●7●22 accept rate: 20%
 0 Yes, you are right @tony_hager answered 25 Jul '16, 00:24 2★kishore1 39●3 accept rate: 0%
 0 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. answered 25 Jul '16, 00:54 3★vigzmv 11 accept rate: 0%
 0 kishore1 the answer for 999999894 is 4. answered 25 Jul '16, 01:28 11 accept rate: 0%
 0 @code_diamond could you put them down.. the four numbers which satisfy the equation for n = 999 999 894 answered 25 Jul '16, 01:34 2★kishore1 39●3 accept rate: 0% 4 999999799 999999814 999999817 999999820 (25 Jul '16, 01:35) sandeep93★
 0 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? answered 25 Jul '16, 01:49 21●2 accept rate: 0%
 0 In this question output of test case 999999969 is 2 in this solution https://www.codechef.com/viewsolution/10893318 while the answer should be 3. Still got AC answered 25 Jul '16, 02:47 3★vinz 1 accept rate: 0%
 0 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? answered 28 Jul '16, 21:44 7★lebron 3.3k●3●17 accept rate: 24%

The following C++ code when compiled gives Time limit exceeded. Can anyone help me out?

# include <iostream>

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; }

1
accept rate: 0%

 -2 You are iterating from n-90 to n.. so, the complexity is O(n).. kindly check it.. answered 25 Jul '16, 00:19 2★kishore1 39●3 accept rate: 0% 6 loop runs just 90 times. So complexity is O(90) :) (25 Jul '16, 00:24) torque6★ sorry yar.. i was in some trance.. so, i was mistaken.. (25 Jul '16, 01:03) kishore12★ indeed it is O(1).. i.e. constant time.. what does O(90) mean?? I was just mistaken.. and someone downvoted my posts.. huh.. (25 Jul '16, 01:13) kishore12★
 -2 yeah.. sorry.. i got it wrong.. now.. it's okay.. answered 25 Jul '16, 00:27 2★kishore1 39●3 accept rate: 0%

I followed the same approach.. But i got WA verdict..

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

2★kishore1
393
accept rate: 0%

 -2 I want to know the test cases u used for testing @Karan Aggarwal answered 25 Jul '16, 00:34 2★kishore1 39●3 accept rate: 0%
 -2 Hello.. anybody here.. whose solution is accepted..?? just run for n= 999 999 894 and tell me ur count.. answered 25 Jul '16, 01:08 2★kishore1 39●3 accept rate: 0%
 -2 Hello.. anybody here whose solution is accepted ?? then run your program for n = 999 999 894 and tell me your count.. answered 25 Jul '16, 01:10 2★kishore1 39●3 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,680
×3,764
×947
×59

question asked: 23 Jul '16, 21:23

question was seen: 5,124 times

last updated: 23 Sep '16, 15:47