# C++ 0ms BFS with unordered_set

• Although one can increase `n` to `n+1` when `n` is odd, `n+1` will be even and will be reduced to `(n+1)/2`. Therefore, the maximum number one can get is not greater than `n+1`.

If we think all the numbers are nodes in a directed graph, where edges are the allowed operations between nodes, this problem can be mapped to a shortest-path problem in an unweighted graph, from node `n` to node `1`.

To write an efficient BFS algorithm, we need to track if a node is visited or not. As the path from any node to `1` is very likely to be `O(log n)`, due to the `n/2` operation. We can store the visited nodes in a set, instead of a binary vector.

One can inspect the number of visited nodes before returning the answer. ( the `clog` statement )

``````#define mp     make_pair
typedef pair<uint32_t,uint32_t> ii;
class Solution {
private:
unordered_set<uint32_t> chk;
public:
int integerReplacement(uint32_t n) {
if( n <= 1 ) return 0;
chk.insert(n);
queue<ii> Q;
Q.push( mp( 0, n ) );
while( !Q.empty() ){
auto p  = Q.front(); Q.pop();
auto d = p.first, m = p.second;
if( m%2 ){
if( !chk.count(m-1) ){
chk.insert(m-1);
Q.push( mp(d+1, m-1 ) );
}
if( !chk.count(m+1) ){
chk.insert(m+1);
Q.push( mp( d+1, m+1) );
}
}else{
if( m/2 == 1 ){
clog << chk.size() << '\n';
return d+1;
}
if( !chk.count(m/2) ){
chk.insert(m/2);
Q.push(mp(d + 1, m / 2));
}
}
}
return -1;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.