JAVA 4ms Solution with Detail Explanation


  • 0
    D

    General idea is how to eliminate all bits from the right.

    If n%2 == 0, we can use n/2, since it eliminate 1 bit per operation, eg. 10->1.

    If n%2 == 1, first choice is using n-1 and n/2, and we use 2 operations to eliminate 1 bit, eg1. 11->10->1, eg.2 x011->x010->x01->x00->x0.
    Another choice is use n+1 and several n/2 to deal with continuous bits 1, but this may not be always better than the above one. eg.1 11->100->10->1, eg.2x011->x100->x10->x1->(x0). Note x1 may form another continuous 1 sequence with potential last bits of 1 in x, and it always no worse than first choice in this situation.

    The truth is for longer continuous 1, second choice is better, and the division is that we have 3+ 1s, or we have some sequence and 011 at the last.

    Here is the codes:

    public class Solution {
        public int integerReplacement(int n) {
            int step = 0, count = 0;
            while(n>0){
                if((n&1)==0) {
                    step +=1;
                    n = n>>1;
                }
                else{
                    while((n&1)!=0){
                        count += 1;
                        n = n>>1;
                    }
                    if(count>2||n!=0&&count==2) {
                        step+=count+1;
                        n = (n|1);
                    } 
                    else step += count<<1;
                    count = 0;
                }
            }
            return step-2;
        }
    }
    

    Note, since we tried to eliminate all bits, and in fact we do not need the last 2 steps, 1->0->, so we return step-2.

    The complexity should be olog(n).


Log in to reply
 

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