SPOJ Problem ONEZERO

Ones and zeros

Explanation:

A very good problem to practice BFS skills. I think that much hint is good to give the problem a shot. Any ways, detailed explanation is provided below.

We start with a value of 1 in the queue for our BFS (referred as queueItem, hereafter). We pop out element from the queue and check if it is divisible by the input 'n'.

• If queueItem is divisible by 'n', we return queueItem.
• Else, we store (queueItem * 10) % 'n' and (queueItem * 10 + 1) % 'n' in the queue.

And, the process continues.

From the solution point of view, I am storing number as set bits and print it out in reverse order at the end. Also, we keep track of modulo values already visited by keeping a visited boolean array, so that we don't end up landing in an infinite loop.

Below is the code for reference.

Solution:

#include <cstdio>
#include <iostream>
#include <utility>
#include <queue>
#include <stack>

typedef long long int LLD;

using namespace std;

queue< pair<LLD, int> > q;
pair<LLD, int> p;

LLD bfs(int n){
    bool visited[20000];
    fill(visited, visited + n, false);
    LLD res;
    q.push(make_pair(1, 1));

    while(!q.empty()){
        p = q.front();
        q.pop();
        visited[p.second] = true;
        if((p.second % n) == 0){
            res = p.first;
            break;
        } else{
            LLD tmp1 = p.first;
            tmp1 <<= 1;
            int modulo = (p.second * 10) % n;
            if(!visited[modulo])
                q.push(make_pair(tmp1, modulo));
            LLD tmp2 = p.first;
            tmp2 <<= 1;
            tmp2 |= 1;
            modulo = (p.second * 10 + 1) % n;
            if(!visited[modulo])
                q.push(make_pair(tmp2, modulo));
        }
    }

    while(!q.empty())
        q.pop();

    return res;
}

void display(LLD n){
    stack<int> s;
    while(n){
        s.push(n % 2);
        n >>= 1;
    }
    while(!s.empty()){
        printf("%d", s.top());
        s.pop();
    }
    printf("\n");
}

int main(){
    int t, n;

    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        LLD result = bfs(n);
        display(result);
    }
    return 0;
}

Any suggestions are welcome.