python, an interesting way


  • 0
    M

    For python, it is convenient to just change the n to binary list, calculate the consecutive '1's in the str, and consider each consecutive '1' sections respectively. For each consecutive '1' section, there are two options, plus one and delete to empty or minus each one to empty.

    class Solution(object):
        def integerReplacement(self, n):
            """
            :type n: int
            :rtype: int
            """ 
            x=bin(n).lstrip('0b');  #get the binary list of integer n;
            l=len(x);
            count=0;    #record the number of consecutive '1's 
            ind=0;      #record the current index in list
            ans=0;      #final answer
            while(ind<l):           #start at the end of the last bit of the number 
                if x[l-1-ind]=='0':
                    if count==0:
                        ans+=1;
                        ind+=1;
                    elif count==1:  #if it is like '01', minus 1 and delete directly
                        ans+=3;
                        ind+=1;
                        count=0;
                    else:           #else plus one and delete all '0's
                        ans+=1+count;
                        count=1;
                        ind+=1;       
                else:               #if the current bit is '1', count plus one
                    count+=1;
                    ind+=1;
                    
            #for the consecutive '1's at the beginning of the list, take the minimum of plus one case and minus each one case        
            if count==1:            
                return ans;
            else:
                return min(ans+2*(count-1), ans+1+count);  
    

Log in to reply
 

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