My 3ms solution using BFS


  • 0
    W

    I personally feel that this is a pretty simple solution if you don't want to use recursion and you don't really feel that you can solve this mathematically during interviews. Basically, we are looking for the shortest path from initial number to the target number. We can use BFS to solve this type of questions. BFS is pretty efficient. Let the length of the shortest path be k, then BFS run in O(k) time.

    This is the 3ms code I have:

    int integerReplacement(int n) {
        // n even n->n/2
        // n odd n->n-1, n+1
        if(n==1)
            return 0;
        queue<long> q; // notice that if you don't use long, you may have overflow when n is INT_MAX
        q.push(static_cast<long>(n));
        // initial distance is zero
        int dist = 0;
        // keep tracks of the elements we have seen
        unordered_set<long> visited;
        visited.insert(n);
       
        // Start BFS      
        while(q.size() ) {
            queue<long> tmp;
            // classic solution if you want to know the depth of BFS
            // use another queue to store the entries for the next round
            while(q.size()) {
                auto next = q.front();
                visited.insert(next);
                q.pop();
                if(next == 1)
                    return rev;
                if((next&1)== 0 && visited.find(next/2) == visited.end()) { 
                    tmp.push(next/2);
                    visited.insert(next/2);
                }
                else {
                    // if n is odd, there are two cases, n-1 or n+1
                    if(visited.find(next-1) == visited.end()){
                        tmp.push(next-1);
                        visited.insert(next-1);
                    }
                    if( visited.find(next+1) == visited.end()) {
                        tmp.push(next+1);
                        visited.insert(next+1);
                    }
                }
            }
            rev ++; 
            swap(q, tmp);
        }
        return -1;
    }

Log in to reply
 

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