PROBLEM LINK:Author: Misha Chorniy 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$. 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$ = $N97$ to $N$ and check which integers satisfy the equation because no integer smaller than $N97$ 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".
asked 23 Jul '16, 21:23

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

complexity is O(90) which you can consider as constant time not O(n). answered 25 Jul '16, 00:25

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

What does O(97) even mean? Shouldn't it be O(1)? answered 28 Jul '16, 18:19

A simpler approach is that, Number 999999999 has the max sum of digits = 81 so 81 + 18 + 9 = 108 so checking from N = 1 to 110 would be enough. answered 25 Jul '16, 00:54

@code_diamond answered 25 Jul '16, 01:34

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

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

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

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; } answered 23 Sep '16, 15:47

yeah.. sorry.. i got it wrong.. now.. it's okay.. answered 25 Jul '16, 00:27

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));
} where is it gone wrong?? answered 25 Jul '16, 00:32

I want to know the test cases u used for testing @Karan Aggarwal answered 25 Jul '16, 00:34

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

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

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