C++ 0ms BFS with unordered_set

  • 0

    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 {
        unordered_set<uint32_t> chk;
        int integerReplacement(uint32_t n) {
          if( n <= 1 ) return 0;
          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) ){
                Q.push( mp(d+1, m-1 ) );
              if( !chk.count(m+1) ){
                Q.push( mp( d+1, m+1) );
              if( m/2 == 1 ){
                clog << chk.size() << '\n';
                return d+1;
              if( !chk.count(m/2) ){
                Q.push(mp(d + 1, m / 2));
          return -1;

Log in to reply

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