Devu and Adding Two Numbers - Editorial

cakewalk
editorial
iitk
wpc
wpc1
wpc1401

#1

Problem link :
contest
practice

Difficulty : Cakewalk

Pre-requisites : AD-hoc

Solution :

First let us make a simple observation. Take example of 10: can we represent it using addition of two positive without having any carry. Answer is No,
we can not, because for creating 0 in the first place, we need to take carry in this case. We can not write it as 0 + 10 because 0 is not positive.

If number is 1 or power of 10, then answer is NO, otherwise answer is YES.

Proof is not that complicated and can be worked out.

You can also iterate over all possible partitions of number n into two positive numbers (ie. total n - 1 partitions) and check whether it is a valid representation
or not.

Complexity of solution will be O(1) if you just check if number if equal to power of 10 or not.

For the second all possible partition solution, your complexity will be (n - 1) * number of digits in n.

Pseudo Code 1

if (n == 1 or n == 10 or n == 100 or n == 1000 or n == 100000)
print YES
else
print NO

Tester’s solution: link


#2

please explain cant we write 5+5=10?


#3

what will be for say 310…, 309+1 here 9+1 will also carry 1… ??


#4

but you can also write…300+10 no carry here…


#5

what about 20?? How will you write it without carry??


#6

@tusharmsrit12 10+10=20


#7

Yes. And this generates a carry !