Hey guys here is a simple problem on BFS of SPOJ. I tried to solve it but getting Run-time error. Here is my Code. At each step i am trying to pick a node from the top of Queue and insert its two children in the queue one appended with 0 and one appended with 1 back in Queue. Could u figure out the error?
I think it's overflow of long long and, as a result, reference to a negative index of the array. Or size of the array is just too small.
Size of array i think is ok. Can u see the problem and tell me my error, its a very easy Problem.
Why are you so sure that your answer will fit to long long? If it doesn't, you can receive negative elements in queue and, thus, p%n will be also negative.
So what to do, dont have data type of bigger range than LONG LONG in C++
Use arrays instead of long long..
I guess this problem can't be solved in such way — even if you provide bigger data type, you'll get TL — brute force will be too slow for 1000 tests. I'd better use dp approach — for each residue 0<=K<n you can store the minimal length of number that consists of 1's and 0's and gives residue K modulo n, and last figure of this number (0 or 1). Thus you can find the minimal number giving residue 0, and it will be the answer.
We need to find multiple => it will be more than our number. So, size of array isn't ok.
Ignore, I was out of my mind obviously. :-)
As you can see at link you provided, you receive RE when test is "1 9999".
how u figured out that i receive RE when test is "1 9999"
P.S.- ok i got it :)
finally got accepted :) Thanks to all of u for ur help