Java Easy To Understand Solution O(n) using Bitwise Shifts


  • 0
    B

    Explanation
    I simply iterate through all the bits of variable num starting from the right-most bit, using bitwise right shifts, and record their complements in a stack. Afterwards, I pop off the bits from the stack to append to our result, using bitwise left shifts.

    Time Complexity
    The time complexity is O(n) where n is the number of bits in num.

    class Solution {
        public int findComplement(int num) {
            Stack<Integer> stack = new Stack<>();
            // Record the complement bits in our stack
            while (num != 0) {
                if (num % 2 == 0) {
                    stack.push(1);
                } else {
                    stack.push(0);
                }
                num = num >> 1;
            }
            // Simply pop off the bits in our stack
            int result = 0;
            while (!stack.isEmpty()) {
                result += stack.pop();
                // If empty stack, we have our final result - don't left shift
                if (!stack.isEmpty()) {
                    result = result << 1;
                }
            }
            return result;
        }
    }
    

Log in to reply
 

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