JAVA 3ms Bit Manipulation Solution


  • 8

    For this problem, if we look at the binary form of each number, we can get the idea that for each '1' (except for the first '1') it counts to two steps, for each '0', it counts to one step.
    So our goal is to use +1 or -1 to reduce steps.

    For example,
    13 = 1101
    If we plus one, we can get 1110; if we reduce one, we can get 1100;
    1110 needs 2+2+1 = 5 steps, while 1100 only needs 2+1+1 = 4 steps, so we choose n-1 in this step.

    Use long to avoid overflow (if n is Integer.MAX_VALUE).

    public class Solution {
        public int integerReplacement(int n) {
            long N = n;
            long small,big;
            int cnt = 0;
            while( N != 1){
            	small = (N  & ( N -1));
            	big = ( N & (N + 1));
            	if( (N & 1) == 0){
            		N >>= 1;
            	}
            	else if ( (small & (small-1)) <= (big & (big-1))){
            		N = N - 1;
            	}
            	else{
            		N = N +1;
            	}
            	cnt++;
            }
            return cnt;
        }
    }
    

  • 9
    K

    Here is my solution with similar idea. When N is odd, only the second bit matters.

    1. If the bit is '1', N+1 will remove at least one '1' in N. 1011 + 1 = 1100, 1111 + 1 = 10000. However, N - 1 will remove only one '1'. 1011 - 1 = 1010 or 1111 - 1 = 1110. So we favor N + 1 here.

    2. If the bit is '0', N+1 will remove zero '1'. 1001 + 1 = 1010. N -1 will remove one '1'. 1001 - 1 = 1000.

    N = 3 is a special case.

    public class Solution {
        public int integerReplacement(int n) {
            long N = n;
            int count = 0;
            while(N != 1) {
                if(N % 2 == 0) {
                    N = N >> 1;
                }
                else {
                    if(N == 3) {
                        count += 2;
                        break;
                    }
                    N = (N & 2) == 2 ? N + 1 : N - 1;
                }
                count ++;
            }
            return count;
    
        }
    }
    

  • 0

    I do not why you do like small = (N & ( N -1)) and (small & (small-1)) <= (big & (big-1)), can you explain?


  • 0

    Similar idea:
    Just check the lowest two digits ...ba,
    IF a is 0, it's a even number, divide by 2
    IF a is 1, it's a odd number, whether to increase or decrease depends on the b

    public int integerReplacement(int n) {
            int count=0;
            while(n>3){
                if((n&1)==1){
                    if((n&2)==2) {
                        n>>=1;
                        n+=1;
                    }
                    else n>>=1;
                    count+=2;
                }else{
                    n>>=1;
                    count++;
                }
            }
            if(n==3) count+=2;
            else if(n==2) count+=1;
            return count;
        }
    

  • 0
    P

    How did you arrive at the conclusion that each set bit contributes 2 to the solution and bit not set contributes 1 to the solution?

    I agree with your Math but I am not sure how you derived it.


  • 0
    This post is deleted!

Log in to reply
 

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