getting wrong answer on spoj problem link:http://www.spoj.com/problems/ONEZERO/ my solution:https://ideone.com/AAS5v4 i came to know that the problem is due to overflow can any one please tell me the efficient solution thanks in advance:) asked 17 Mar '15, 00:08

this problem can be solved using bfs using states. So the naive state approach is that we start from 1 and then we have two options either append 0 or 1 to the current number.
1 > (10,11)>(100,101,110,111)>......
every time when we encounter any number we can check off that module with n gives 0, but this solution will give us overflow or a TLE.
so we can optimize it, as we can go from one state to another state by just appending the 0 or 1, now let's say we have already found a string (X) of 0 and 1 whose modulus with n giving me some value p. Now during my traversal to all possible outcome if I encounter another string (Y) which is greater than X and giving the same modulus p. I can ignore it as if both of them giving the same modulus result, as I assume If I append Z both of them going me the same result. In this way, I'm only considering n states, this solves our TLE problem.
Kindly find my ideone solution. https://ideone.com/JDnBN5 answered 01 Feb '17, 08:50
