C++ 0ms BFS with unordered_set


  • 0
    Y

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

Log in to reply
 

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