3 ms elegant C++ Code with explanation


  • 1

    The basic idea is to use recursion with memory since there are many duplicated sub-cases.
    To avoid the INT_MAX case, we just go step further with 1 + res[1+(n/1)] instead of res[n+1)/2]

        int integerReplacement(int n) {
            if(n==1) return 0;
            else if(n==2) return 1;
            static unordered_map<int, int> map_n_cnt;
            
            if( map_n_cnt[n] != 0 ) return map_n_cnt[n];
            if( (n&1) == 0 ) {
                map_n_cnt[n] = 1 + integerReplacement(n>>1);
                return map_n_cnt[n];
            }
            else{
                map_n_cnt[n] = 1 + std::min( integerReplacement(n-1), 1+integerReplacement(1+(n>>1)) );
                return map_n_cnt[n];
            }
        }
    
    

Log in to reply
 

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