I am just starting with CP. So I am practising the easy question. Came accross this question which in itself has title very easy problem. 
Here the input is known, hence every one is posting the cout/print version of answer. I have gone through 10-15 submission which have AC status, each one is just printing the answer. No one has solved it with logic. I myself is trying for 2 days now. With no luck.
Is someone here who’s smart enough to find a generic solution. (Or may be this question cannot have a generic solution hence they have given the input hardcoded)
I have also got the logic and I too can just write 7 couts but thats not what i am looking for. even after finding the pattern i am not able to convert it in generic code which would print same pattern for any number. Thats why came here.
Yes, there is a generic solution. The first step is to decompose the given number into the powers of 2 that sum to it. For example, 137 = 2^7 + 2^3 + 2^0. Then, you’d want to write it in their stupid format: 2(7)+2(3)+2(0). This almost works, but you can’t use 3 and 7. How do you write those numbers in their format? Do the same thing! 7 = 2^2 + 2^1 + 2^0, which is representable as 2(2)+2+2(0), and 3 = 2^1 + 2^0, which is representable as 2+2(0). Luckily, this time we get numbers in their format, so we stop. Replacing the numbers with their formatted versions, we get a final string of 2(2(2)+2+2(0))+2(2+2(0))+2(0). This will work for all numbers.
This has a relatively nice implementation with recursion. Here’s my submission to prove that it works (although I had to minify it to fit it in their stupid 500 byte submission size limit), and regularly formatted code. I think the worst-case complexity is something around O(\log{n}\log\log{n}) for a number of the form 2^n - 1.
4 Likes
Thanks @galencolin. This is what I was trying to do. My recursive solution was always having one extra (.
Great Work 