# Can anyone find generic solution to this question? no editorial provided (EASYPROB)

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 