SPOJ 370 - Ones and zeros (ONEZERO)

Question

I am trying to solve SPOJ problem "Ones and zeros":

Certain positive integers have their decimal representation consisting only of ones and zeros, and having at least one digit one, e.g. 101. If a positive integer does not have such a property, one can try to multiply it by some positive integer to find out whether the product has this property.

My approach to this problem was simply doing BFS. Taking string containing only '1' and then doing BFS with it and at each step adding '1' and '0'. Keeping track of number in string form and remainder till now. When remainder is zero, the number was found.

My problem is: My code is taking too long for test cases e.g. 9999 or 99999. How can I improve the runtime 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 give the points why your code is slower

1. As sukunrt said you need to keep an array visited of size n, where you can mark the currently obtained modulus as visited so that you don't visit it again, because if you are at an already visited modulus you don't need to consider the part of string obtained till now as it only makes the number larger(we need minimum), i.e it means once you visit a modulus you say x then you find the least number composed of 0 and 1 that gives x as remainder when divide by n.

2. You always pass the string so obtained to the child, which not only increase the memory but time too. To avoid this, just take two more arrays say value[] and parent[] both of size n.

   parent[i] stores the parent modulus of modulus i.

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

   In the end you can just backtrack to form the whole number just for modulus=0.

   Also after making changes, your code will give WA because you have to first push the child obtained by appending '0' at end and then the child obtained by appending '1' at end. (You can prove it yourself).

Answer 2

Here's a hint. think about it this way:

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

So you need to store only N states i.e. 0-n-1. Start with 1. and do the bfs. You need to discard the branches that have the same remainder as before. I'll leave the proof to you.