Binary

Last updated 1 year ago

Binary

11. Sum of Two Integers

Problem Description: The problem is to calculate the sum of two integers without using the '+' or '-' operators. The problem on LeetCode can be found here:
Optimized Java Code:

public class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
}

Algorithm Explanation: The approach to solve this problem is to use bit manipulation. We can use the bitwise exclusive OR (XOR) operator (^) to perform addition without considering the carry. The bitwise AND operator (&) gives us the bits that need to be carried over. We iterate until there is no carry left (b becomes 0). In each iteration, we calculate the carry by performing a bitwise AND operation between a and b, and then shifting it one position to the left (<< 1) to get the carry. The sum of a and b without considering the carry is calculated using the bitwise XOR operation (a ^ b). We update a to hold the sum and b to hold the carry. Finally, we return the value of a as the total sum.

During an interview, it is important to explain the algorithm step by step and emphasize the key points such as XOR for addition and AND for carry. Additionally, explain how the carry is propagated to the next iteration.

Problem Abstractions: This algorithm can be used for other problems that involve performing addition using bitwise operators, without using the '+' or '-' operators. It can be applied in scenarios where the use of arithmetic operations is prohibited or when optimizing for performance by reducing the number of operations.
Similar Problems: a. Add Two Numbers:

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode p = l1, q = l2, curr = dummyHead;
        int carry = 0;
        
        while (p != null || q != null) {
            int x = (p != null) ? p.val : 0;
            int y = (q != null) ? q.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (p != null) p = p.next;
            if (q != null) q = q.next;
        }
        
        if (carry > 0) {
            curr.next = new ListNode(carry);
        }
        
        return dummyHead.next;
    }
}

Description: This problem requires adding two numbers represented as linked lists rather than integers. The carry is propagated during the addition of each digit.

public class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int carry = 0;
        int i = a.length() - 1, j = b.length() - 1;
        
        while (i >= 0 || j >= 0) {
            int sum = carry;
            if (i >= 0) {
                sum += a.charAt(i--) - '0';
            }
            if (j >= 0) {
                sum += b.charAt(j--) - '0';
            }
            sb.append(sum % 2);
            carry = sum / 2;
        }
        
        if (carry != 0) {
            sb.append(carry);
        }
        
        return sb.reverse().toString();
    }
}

Description: This problem requires adding two binary numbers represented as strings. The carry is propagated during the addition of each bit.

12. Number of 1 Bits

Problem Description:

The problem "Number of 1 Bits" asks us to count the number of 1 bits in a given integer.

Leetcode link: https://leetcode.com/problems/number-of-1-bits/

Optimized Java Code:

public class NumberOf1Bits {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            count++;
            n = n & (n - 1);
        }
        return count;
    }

    public static void main(String[] args) {
        NumberOf1Bits solution = new NumberOf1Bits();
        int n = 11;
        System.out.println("Number of 1 bits in " + n + ": " + solution.hammingWeight(n));
    }
}

Algorithm Explanation:

The algorithm uses a bitwise AND operation to eliminate the rightmost 1 bit of the given integer n in each iteration. We keep a counter to count the number of 1 bits encountered so far. The process continues until n becomes zero.

At each iteration, n is updated by performing a bitwise AND operation between n and n-1. This operation sets the rightmost 1 bit of n to zero and retains all other bits. As a result, the algorithm eliminates one 1 bit in each iteration. By continuing this process until n becomes zero, we count all the 1 bits.

Abstracted Problems:

The similar algorithm of counting the number of 1 bits can be applied to various problems involving bit manipulation and counting.

Some possible abstracted problems include:

Calculate the parity (whether the number of 1 bits is odd or even) of a given integer.
Find the position of the rightmost (or leftmost) 1 bit in a given integer.
Count the number of 1 bits in multiple integers in an array or a list.

Similar Problems with Solutions:

Here are some similar problems along with their solutions:

public int singleNumber(int[] nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

public int reverseBits(int n) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        result <<= 1;
        result |= n & 1;
        n >>= 1;
    }
    return result;
}

public int[] countBits(int n) {
    int[] result = new int[n+1];
    for (int i = 1; i <= n; i++) {
        result[i] = result[i >> 1] + (i & 1);
    }
    return result;
}

These are just a few examples, and there are many more problems that can benefit from similar bit manipulation techniques.

13. Counting Bits

The problem is called "Counting Bits" and the link to the problem on LeetCode is https://leetcode.com/problems/counting-bits/.
Here is the optimized Java code for the "Counting Bits" problem:

public class Solution {
    public int[] countBits(int num) {
        int[] result = new int[num + 1];
        
        for (int i = 1; i <= num; i++) {
            // If i is odd, it has the same number of 1s as i/2 plus 1
            if (i % 2 == 1) {
                result[i] = result[i/2] + 1;
            } else {
                // If i is even, it has the same number of 1s as i/2
                result[i] = result[i/2];
            }
        }
        
        return result;
    }
}

Algorithm and Explanation:

We need to compute the number of 1s in the binary representation for each number from 0 to num.
Initialize an array result of size num + 1 to store the results.
For each number i from 1 to num, we have the following observations:
- If i is odd, it has the same number of 1s as i/2 plus 1. This is because if a number is odd, its binary representation ends with a 1, and when you divide it by 2, the remaining binary representation is the same as i/2, but with an extra 1 at the end.
- If i is even, it has the same number of 1s as i/2. This is because if a number is even, its binary representation ends with a 0, and when you divide it by 2, the remaining binary representation is the same as i/2.
We can utilize these observations to efficiently compute the number of 1s in each number from 1 to num.
The time complexity of this solution is O(num).

Similar Problems: This algorithm can be used in problems that involve counting the number of set bits in the binary representation of a number. Some examples include:

Hamming Weight (https://leetcode.com/problems/number-of-1-bits/)
Reverse Bits (https://leetcode.com/problems/reverse-bits/)

Similar Problems with Detailed Java Code and Descriptions:

Hamming Weight (Number of 1 Bits):

public class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        
        while (n != 0) {
            count += n & 1;
            n >>>= 1;
        }
        
        return count;
    }
}

In this problem, we need to count the number of 1 bits in the binary representation of a given integer n. We can use a bit manipulation technique known as bit shifting to check the rightmost bit of n at each iteration. If the rightmost bit is 1, we increment the count. After checking the rightmost bit, we shift n to the right by 1 position using the unsigned right shift operator >>>. The loop continues until n becomes 0. The time complexity of this solution is O(log n), where n is the number of bits in the input integer.

Reverse Bits:

public class Solution {
    public int reverseBits(int n) {
        int result = 0;
        
        for (int i = 0; i < 32; i++) {
            result <<= 1; // Left shift result by 1 position
            result |= n & 1; // Set the rightmost bit of result to the rightmost bit of n

            n >>= 1; // Right shift n by 1 position
        }
        
        return result;
    }
}

In this problem, we need to reverse the bits of a given 32-bit unsigned integer n. We can solve this problem by using the same bit shifting technique as in the previous problems. We initialize a variable result to store the reversed bits. We iterate 32 times and at each iteration, we left shift result by 1 position, set the rightmost bit of result to the rightmost bit of n using the bitwise OR operator |, and right shift n by 1 position. Finally, we return the reversed integer result. The time complexity of this solution is O(1) since the number of iterations is fixed.

14. Missing Number

Problem Description:

The problem "Missing Number" on LeetCode asks us to find the missing number in an array. Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

LeetCode link: https://leetcode.com/problems/missing-number/

Optimized Java Code:

Here's the optimized Java code for the "Missing Number" problem with detailed comments:

class Solution {
    public int missingNumber(int[] nums) {
        int missing = nums.length; // Initialize missing as the last possible number
        
        for (int i = 0; i < nums.length; i++) {
            missing ^= i ^ nums[i]; // Use XOR operator to get the missing number
        }
        
        return missing;
    }
}

Algorithm Description:

The approach used in the optimized code is based on XOR operations. The missing number can be found by performing XOR (^) on all elements from 0 to n and the elements in the input array.

To explain the algorithm, let's consider an example: nums = [3, 0, 1].

We initialize missing as 3, which is the last possible number in the given array.

In the for loop, we'll be XOR-ing the index (0, 1, 2) and the corresponding element in the array (3,0,1). The XOR operation has the property of being associative and commutative.

First iteration: missing ^= 0 ^ 3 => missing = 3 ^ 0 ^ 3 => missing = 0 (We remove '3' from the missing number)
Second iteration: missing ^= 1 ^ 0 => missing = 0 ^ 1 ^ 0 => missing = 1 (We remove '0' from the missing number)
Third iteration: missing ^= 2 ^ 1 => missing = 1 ^ 2 ^ 1 => missing = 2 (We remove '1' from the missing number)

After the loop, the 'missing' value will be the actual missing number, which in our example is 2.

The time complexity of this solution is O(n), where n is the length of the input array.

Generalization of Algorithm:

The XOR-based approach used in the "Missing Number" problem can be abstracted to solve similar problems where we need to find the missing element(s) or perform operations efficiently. Some problems that can be solved using a similar algorithm include:

Single Number: Given an array of integers where every element appears twice, except for one. Find that single number.
Two Single Numbers: Given an array of numbers where two elements appear only once, and all the other elements appear twice, find the two elements that appear only once.
Bitwise-AND of Numbers Range: Given a range [m, n] where 0 <= m <= n <= 2^31 - 1, return the bitwise AND of all numbers in this range, inclusive.

Similar Problems:

Here are some similar problems with detailed Java code and descriptions:

5.1 Single Number:

Problem Description:

Given a non-empty array of integers where every element appears twice except for one. Find that single number.

LeetCode link: https://leetcode.com/problems/single-number/

Java Code:

class Solution {
    public int singleNumber(int[] nums) {
        int single = 0;
        
        for (int num : nums) {
            single ^= num;
        }
        
        return single;
    }
}

Explanation:

Similar to the "Missing Number" problem, we use the XOR operator to find the single number. Since XOR-ing a number with itself results in 0, all the duplicate numbers cancel each other out, leaving only the single number.

5.2 Two Single Numbers:

Problem Description:

Given an array of numbers where two elements appear only once and all the other elements appear twice, find the two elements that appear only once.

LeetCode link: https://leetcode.com/problems/single-number-iii/

Java Code:

class Solution {
    public int[] singleNumber(int[] nums) {
        int bitmask = 0;
        
        for (int num : nums) {
            bitmask ^= num;
        }
        
        int diff = bitmask & (-bitmask);
        
        int[] result = new int[2];
        result[0] = 0;
        result[1] = 0;
        
        for (int num : nums) {
            if ((diff & num) == 0) {
                result[0] ^= num;
            } else {
                result[1] ^= num;
            }
        }
        
        return result;
    }
}

Explanation:

In this problem, we first calculate the XOR of all the numbers in the array. The result will be the XOR of the two single numbers because the duplicate numbers cancel each other out. We then find the rightmost set bit in the XOR result using bitmask & (-bitmask). This will give us a bit where the two single numbers differ.

Then, we iterate through the array again and split the numbers into two groups: one group where the bit at the diff position is 0, and the other group where it is 1. We XOR all the numbers in each group separately, resulting in the two single numbers.

Note: Both single numbers will be stored in the result array.

5.3 Bitwise-AND of Numbers Range:

Problem Description:

Given a range [m, n] where 0 <= m <= n <= 2^31 - 1, return the bitwise AND of all numbers in this range, inclusive.

LeetCode link: https://leetcode.com/problems/bitwise-and-of-numbers-range/

Java Code:

class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        
        while (m < n) {
            m >>= 1;
            n >>= 1;
            shift++;
        }
        
        return m << shift;
    }
}

Explanation:

In this problem, we're interested in finding the common prefix of the binary representations of the given numbers. By right-shifting both m and n until they become equal, we identify the common prefix. The number of right shifts required is stored in the shift variable. Finally, we left-shift m by shift positions to obtain the result.

Note: The common prefix represents the bits that are the same among all numbers in the range, and the trailing zeros are not affected by the right shifts. Therefore, we can preserve the zeros by left-shifting m by shift positions.

15. Reverse Bits

Problem Description: The problem is to reverse the bits of a given 32-bit unsigned integer.
Optimized Java Code for Reverse Bits:

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int reversed = 0;
        
        for (int i = 0; i < 32; i++) {
            reversed <<= 1;         // Left-shift reversed by 1 (same as multiplying by 2)
            reversed |= (n & 1);    // Set the least significant bit of reversed to n's least significant bit
            n >>= 1;                // Right-shift n by 1 (same as dividing by 2)
        }
        
        return reversed;
    }
}

Algorithm Explanation:
The algorithm uses bitwise operators to reverse the bits of the given 32-bit unsigned integer 'n'.
- We initialize reversed as 0, which will hold the bits in reversed order.
- We iterate from bit 0 to bit 31 (32 bits in total) using a loop.
- In each iteration, we left-shift reversed by 1 (same as multiplying by 2). This makes space for the new bit that we are going to append.
- To determine the new bit, we use bitwise AND (n & 1) to get the least significant bit of n. If this bit is 1, we set the corresponding bit in reversed by using bitwise OR (reversed |= (n & 1)).
- Finally, we right-shift n by 1 (same as dividing by 2), so that the next iteration will consider the next bit of n.
Abstracted Problems:
The same algorithm can be used to solve problems related to bit manipulation, such as:
- Counting the number of set bits (1s) in an integer.
- Finding the next highest power of 2 for a given integer.
- Checking if a number is a power of 2.
- Reversing the bits in a byte, short, or long integer.

Similar Problems with Java Code and Descriptions:

Description: Given an unsigned integer, return the number of '1' bits it has.

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        
        while (n != 0) {
            count += (n & 1);    // Add the least significant bit to the count
            n >>>= 1;            // Unsigned right-shift n by 1
        }
        
        return count;
    }
}

Description: Given an integer n, return true if it is a power of two. Otherwise, return false.

public class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0) {
            return false;
        }
        
        return (n & (n - 1)) == 0;    // Powers of 2 have only 1 bit set, so n & (n-1) should be 0
    }
}

Description: Given a byte, reverse its bits and return the resulting byte.

public class Solution {
    public byte reverseBits(byte n) {
        byte reversed = 0;
        
        for (int i = 0; i < 8; i++) {
            reversed <<= 1;
            reversed |= (n & 1);
            n >>= 1;
        }
        
        return reversed;
    }
}

PreviousArray NextDynamic Programming

Last updated 1 year ago