ONE_ZERO SPOJ 

http://www.spoj.com/problems/ONEZERO/


It's very important to make a visited array [1...n], so that the number which is visited once will not be visited again, if we would not make this visited it will definitely lead to TLE :P (idea credit kishlay )


solution


#include<bits/stdc++.h>

using namespace std;

string bfs(int n)
{

 pair<int,string> temp;
 queue<pair<int,string> > st;
 st.push(make_pair(1,"1"));
 int visited[n];
 for(int i=0;i<n;i++) visited[i]=0; visited[1]=1;

 while(!st.empty())
 {
  string tt1,tt2;
  temp=st.front();
  st.pop();
  if(temp.first%n!=0)
  {
    tt1=temp.second+"0";
    //cout<<tt<<" ";
    if(visited[(temp.first*10)%n]==0){
    st.push(make_pair((temp.first*10)%n,tt1));
    visited[(temp.first*10)%n]=1;}

     tt2=temp.second+"1";
    if(visited[(temp.first*10+1)%n]==0){
    st.push(make_pair((temp.first*10+1)%n,tt2));
    visited[(temp.first*10+1)%n]=1;}
  }
  else
  {
    return temp.second;
  }
 }
}

int main()
{
 int t;
 cin>>t;
 while(t--)
 {
  int n;
  cin>>n;
  string pp=bfs(n);
  cout<<pp<<endl;
 }
return 0;
}

Comments

Popular posts from this blog

Getting Started With MEAN App Development with AngularJs , ExpressJs , NodeJs and MongoDB.

B. Dreamoon and WiFi :calculate no. of ways : recursive solution (branch and bound )

A. Dreamoon and Stairs : minimum steps to reach : recursion solution.