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