There is a natural number n. You have to find a pair of natural numbers x, y whose sum is n and also have the least energy among other pairs having the sum n. Then output the sum of digits of the pair.
Energy(x) = sum of all digits of x
Total Energy = Energy(x) + Energy(y)
1 <= n <= 10^9
For eg,
n = 10000
A few pairs:
5000 + 5000 -> Energy = 10
1000 + 9000 -> Energy = 10
9999 + 1 -> Energy = 37
2999 + 7001 -> Energy = 37
So possible answers are:
(5000, 5000), (1000, 9000) etc
And Final answer is 10.IT is not a SPOJ problem. I just came across this problem and wanted to share the tricky solution behind it.
Solution :
If n is of type 10^x then the answer is 10. Otherwise answer is the sum of digits of n.
The idea here is to break down the number into a pair containing digits less than that are present in n. if you break down into smaller digits then sum remains the same as the original number. example for 7= 1-6,2-5,3-4.
for a number like 100, 1000.... digit 1 can’t be broken down into further pairs, so we try to make 10 as the sum of digit so that the sum becomes n. like for 10=5-5,2-8,3-7 100=20-80,40-60
for other numbers, like 123 it can be broken into 100-23, 120-3, 111-12... all will give you sum 6. which is the sum of digits of the original number.
if you try to break down into further pairs like 80-43, 52-71, you will see that the digit sum increases as you have broken down to a number containing digits which are higher than those are present in n. like 8 4,5,7 are greater than 3.
