getting wrong answer on spoj problem link:SPOJ.com - Problem ONEZERO
my solution:AAS5v4 - Online C++ Compiler & Debugging Tool - Ideone.com
i came to know that the problem is due to overflow
can any one please tell me the efficient solution thanks in advance:)
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.
eg:
n = 15
X: 1010
Y: 1100
X%n = 5
Y%n = 5
so if we encounter initially to 1010, we will ignore 1100 as both of them will finally give the same result.
To solve overflow problem, we don’t have to store the whole number, we can store parent of every number and store the value i.e 1 or 0 is used to get from parent to current.
Kindly find my ideone solution.
2 Likes