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;
}
};
```