SPOJ 370 - OSTs and Zeros (ONEZERO)

Question

I am trying to solve the Osty and Zeros SPOJ problem :

Some positive integers have a decimal notation consisting of only ones and zeros and having at least one digit, for example. 101. If a positive integer does not have this property, you can try to multiply it by some positive integer to find out if this property has a property.

My approach to this problem was simple BFS. Taking a line containing only '1' , and then run BFS with it, and add '1' and '0' at each step. Tracking the quantity as a string and balance so far. When the remainder is zero, a number was found.

My problem: my code is too long for test cases, for example. 9999 or 99999. How can I improve the execution time of the algorithm?

 // Shashank Jain /* BFS */ #include <iostream> #include <cstdio> #include <cstring> #include <climits> #include <string> #include <algorithm> #include <vector> #include <cmath> #include <queue> #include <stack> #define LL long long int using namespace std; LL n; string ans; void bfs() { string str,first,second; str+='1'; // number will start with '1' always if(n==1) { ans=str; return; } queue<pair<string,LL> >q; // pair of STRING(number) and long long int // (to hold remainder till now) pair<string,LL>p; p=make_pair(str,1); q.push(p); LL rem,val,temp; while(q.empty()==0) { p=q.front(); q.pop(); str=p.first; val=p.second; if(val==0) // remainder is zero means this is number { ans=str; return ; } // adding 1 to present number temp=val*10+1; rem=(temp)%n; firstone=str+'1'; p=make_pair(firstone,rem); q.push(p); // adding 0 to present number temp=val*10+0; rem=(temp)%n; secondone=str+'0'; p=make_pair(secondone,rem); q.push(p); } } int main() { int t,i; scanf("%d",&t); while(t--) { scanf("%lld",&n); bfs(); for(i=0;i<ans.size();i++) { printf("%c",ans[i]); } printf("\n"); } return 0; } 

Answer 1

I just solved the problem. I would not post my snippet, but I will talk about why your code is slower.

• As sukunrt said, you need to save the array visited by size n, where you can mark the currently received module as visited so that you do not visit it again, because if you are already with the visit module, you do not need to consider the part of the string received so far, since it only increases the number (we need a minimum), i.e. means that when you visit the module you say x , then you will find the smallest number consisting of 0 and 1 which gives x as the remainder when divided by n.

• You always pass the received string to the child, which not only increases memory, but also time. To avoid this, just take two more arrays: value[] and parent[] both sizes n.

  parent[i] stores the module of the parent module with module i .

  value[i] stores the current bit corresponding to module i (0 <= i <n).

  In the end, you can simply step back to form an integer only for module = 0.

  Also, after making your changes, your code will provide WA, because you must first click on the child element by adding “0” at the end, and then get the child by adding “1” at the end. (You can prove it yourself).

Answer 2

Here is a hint. think of it this way:

Suppose the number you want is X. X mod N = 0.

So, you need to save only N states, i.e. 0-n-1. Start with 1. and run bfs. You need to drop branches that have the same remainder as before. I will leave you a proof.