Java, O(N) solution, easy to understand with detailed explanation and comments


  • 0

    idea is simple, check each bit from right to leftmost bit 1, if bit is 1, continue, if bit is 0, set result's corresponding bit to 1

    public class Solution {
        public int findComplement(int num) {
            int result = 0;
            //use set to set the value of result in each bit
            int set = 1;
            while(num != 0) {
                //if last bit is 0 , set corresponding position of result to 1
                if((num&1)== 0) {
                    result |= set;
                }
                //if last bit of num is 1, then do not need to set result
                set <<= 1; // left shift 1 bit
                num >>= 1;//right shift num, move right 1 bit
            }
            return result;
        }
    }

Log in to reply
 

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