Bit Manipulation

Minimum Bit Flips to Convert Number

class Solution {
    public int minBitsFlip(int start, int goal) {
        int xor = start ^ goal;
 
        int res = 0;
        while (xor != 0) {
            res += (xor & 1);
            xor = xor >> 1;
        }
 
        return res;
    }
}

The algorithm calculates the minimum bit flips required to convert start to goal. It first computes the XOR of start and goal. The set bits in the resulting xor value represent the differing bits between the two numbers. The method then counts these set bits by repeatedly checking the last bit and right-shifting.

Time Complexity: O(log N), where N is the maximum value of the inputs, as the loop runs for each bit.

Space Complexity: O(1).

Single Number - I

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
 
        for (var x : nums) {
            res ^= x;
        }
 
        return res;
    }
}

This algorithm finds the unique element in an array where all other elements appear twice. It leverages the XOR property a ^ a = 0 and a ^ 0 = a. By XORing all elements together, the pairs of identical numbers cancel out, leaving only the single, unique number.

Time Complexity: O(n), as it requires a single pass through the array.

Space Complexity: O(1).

Single Number - II

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
 
        for (int i = 0; i < 32; ++i) {
            int countBits = 0;
 
            for (var x : nums) {
                if ((x & (1 << i)) != 0) {
                    ++countBits;
                }
            }
 
            if (countBits % 3 != 0) {
                res |= (1 << i);
            }
        }
 
        return res;
    }
}

This algorithm finds the single element that appears once in an array where every other element appears three times. It iterates through each of the 32 bits of an integer. For each bit, it counts the total number of times it is set across all elements. If a bit's total count is not a multiple of three, it must belong to the unique number. These bits are then combined to form the result.

Time Complexity: O(n), specifically O(32 * n), since it iterates through all numbers for each of the 32 bits.

Space Complexity: O(1).

Single Number - III

class Solution {
    public int[] singleNumber(int[] nums) {
        int allXor = 0;
        for (int x : nums) {
            allXor ^= x;
        }
 
        int setBit = (allXor & (allXor - 1)) ^ allXor;
 
        int a = 0;
        int b = 0;
        for (int x : nums) {
            if ((x & setBit) != 0) {
                a ^= x;
            } else {
                b ^= x;
            }
        }
 
        return new int[]{Math.min(a, b), Math.max(a, b)};
    }
}

This algorithm finds two unique elements in an array where all other elements appear twice. First, it XORs all numbers to get a ^ b. Then, it finds a set bit in this result, which indicates a bit position where a and b differ. The array is then partitioned into two groups based on this bit. XORing all elements in each group separately reveals a and b.

Time Complexity: O(n), as it involves a few passes through the array.

Space Complexity: O(1).

Divide two numbers without multiplication and division

class Solution {
    public int divide(int dividend, int divisor) {
        boolean isNegative = false;
 
        if ((dividend >= 0 && divisor < 0) || (dividend <= 0 && divisor > 0)) {
            isNegative = true;
        }
 
        long n = Math.abs((long) dividend);
        long d = Math.abs((long) divisor);
 
        int res = 0;
        while (n >= d) {
            int count = 0;
 
            while (n >= (d << (count + 1))) {
                ++count;
            }
            res += (1 << count);
            n -= (d << count);
        }
 
        if(res == (1 << 31) && !isNegative) {
            return Integer.MAX_VALUE;
        }
        if(res == (1 << 31) && isNegative) {
            return Integer.MIN_VALUE;
        }
 
        return isNegative ? -1 * res : res;
    }
}

This algorithm divides two integers using only bitwise operations, simulating long division in binary. It repeatedly subtracts the largest possible power-of-two multiple of the divisor from the dividend. The quotient is built by summing up these powers of two. It handles signs and integer overflow edge cases.

Time Complexity: O((log n)²), where n is the dividend.

Space Complexity: O(1).

Power Set Bit Manipulation

class Solution {
    public List<List<Integer>> powerSet(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
 
        for (int i = 0; i < (1 << nums.length); ++i) {
            List<Integer> curr = new ArrayList<>();
 
            for (int j = 0; j < nums.length; ++j) {
                if ((i & (1 << j)) != 0) {
                    curr.add(nums[j]);
                }
            }
 
            res.add(curr);
        }
 
        return res;
    }
}

This method generates all subsets (the power set) of a given array. It iterates from 0 to 2ⁿ-1. Each integer i in this range represents a unique subset, where the j-th bit of i being set corresponds to including the j-th element of the input array in the subset.

Time Complexity: O(n * 2ⁿ), where n is the number of elements in nums.

Space Complexity: O(n * 2ⁿ), to store all the generated subsets.

XOR of numbers in a given range

class Solution {
    public int findRangeXOR(int l, int r) {
        return xorTillN(l - 1) ^ xorTillN(r);
    }
 
    private int xorTillN(int n) {
        if (n % 4 == 1) return 1;
        if (n % 4 == 2) return n + 1;
        if (n % 4 == 3) return 0;
        return n;
    }
}

This algorithm computes the XOR sum of all numbers in a given range [l, r]. It uses the property that XOR(l, r) = XOR(0, r) ^ XOR(0, l-1). The xorTillN helper function calculates the XOR sum from 0 to n in constant time by exploiting a repeating pattern based on n mod 4.

Time Complexity: O(1).

Space Complexity: O(1).