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'.
Solution: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.
#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.