You are not logged in. Please login at www.codechef.com to post your questions!

×

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

This question is marked "community wiki".

asked 23 Jul '16, 21:23

pushkarmishra's gravatar image

4★pushkarmishra
1.3k156581
accept rate: 4%

edited 25 Jul '16, 00:54

3

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

(25 Jul '16, 00:13) tony_hager5★

13

S(S(x)) can be maximum 16, not 9!!! Because of S(X) <= 81, but it's also can be 79 as well.

link

answered 25 Jul '16, 00:33

meirambek's gravatar image

3★meirambek
712
accept rate: 0%

Corrected. Thank you

(25 Jul '16, 00:55) pushkarmishra4★

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

link

answered 25 Jul '16, 00:25

rohit_0801's gravatar image

4★rohit_0801
3049
accept rate: 10%

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

link

answered 25 Jul '16, 00:38

lohit_97's gravatar image

4★lohit_97
3428
accept rate: 4%

What does O(97) even mean? Shouldn't it be O(1)?

link

answered 28 Jul '16, 18:19

ista2000's gravatar image

4★ista2000 ♦
2.4k722
accept rate: 20%

Yes, you are right @tony_hager

link

answered 25 Jul '16, 00:24

kishore1's gravatar image

2★kishore1
393
accept rate: 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.

link

answered 25 Jul '16, 00:54

vigzmv's gravatar image

3★vigzmv
11
accept rate: 0%

kishore1 the answer for 999999894 is 4.

link

answered 25 Jul '16, 01:28

code_diamond's gravatar image

4★code_diamond
11
accept rate: 0%

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

link

answered 25 Jul '16, 01:34

kishore1's gravatar image

2★kishore1
393
accept rate: 0%

4 999999799 999999814 999999817 999999820

(25 Jul '16, 01:35) sandeep93★

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?

link

answered 25 Jul '16, 01:49

hitman333's gravatar image

2★hitman333
212
accept rate: 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

link

answered 25 Jul '16, 02:47

vinz's gravatar image

3★vinz
1
accept rate: 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?

link

answered 28 Jul '16, 21:44

lebron's gravatar image

7★lebron
3.3k317
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; }

link

answered 23 Sep '16, 15:47

pratiktsingh17's gravatar image

1★pratiktsingh17
1
accept rate: 0%

-2

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

link

answered 25 Jul '16, 00:19

kishore1's gravatar image

2★kishore1
393
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..

link

answered 25 Jul '16, 00:27

kishore1's gravatar image

2★kishore1
393
accept rate: 0%

-2

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

link

answered 25 Jul '16, 00:32

kishore1's gravatar image

2★kishore1
393
accept rate: 0%

-2

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

link

answered 25 Jul '16, 00:34

kishore1's gravatar image

2★kishore1
393
accept rate: 0%

-2

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

link

answered 25 Jul '16, 01:08

kishore1's gravatar image

2★kishore1
393
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..

link

answered 25 Jul '16, 01:10

kishore1's gravatar image

2★kishore1
393
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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