LeetCode Blind 75 - Part 2

07 Jun 2021

In this blog I’ll be posting the codes (C++) and hints for the Bitwise manipulation related questions. You can find the link to the curated Blind-75 link here.
Before that, here’s a few resources that helped me solve these questions!

1. Sum of two integers

Problem Given two integers a and b, return the sum of the two integers without using the operators + and -.

Hint: Using the logic of a Half adder (AND and XOR gates for carry and sum).

class Solution {
public:
    int getSum(int a, int b) {
if (b==0) return a;
    int sum = a^b; // finding the sum
    int carry = (unsigned int)(a & b)<<1; // finding the carry
    return getSum(sum, carry);
}
};

2. Number of 1 bits

Problem Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).

Hint: Checking for the right most bit and then doing right shift.

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

3. Counting Bits

Problem Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

Hint: Calculating the number of 1s using the same logic from previous question.

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> ans;
        for(int i=0; i<n+1; i++){
                if(i==0)
                    ans.push_back(0);
            else{
                int temp = i;
                int count = 0;
                while(temp>0){
                    count += (temp&1);
                    temp= temp>>1;
                }
                ans.push_back(count);
            }
        }
        return ans;
        
    }
};

4. Missing Number

Problem Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Hint: Using the property of XOR that a ^ a = 0.

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ans = 0;
        for(int i=0; i<nums.size(); i++){
            int temp = nums[i]^i;
            ans = ans ^ temp;
        }
        return ans^nums.size();
    }
};

5. Reverse Bits

Problem Reverse bits of a given 32 bits unsigned integer.

Hint: Fixing the right most bit in the answer from the number and then shifting the answer to left and given number to right.

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        int ans = 0;
        for(int i=0; i<32; i++){
            ans= ans<<1;
            ans= ans|(n&1);
            n = n>>1;
        }
        return ans;
    }
};

Thats all for now! I’m always up for a conversation, you can email me - either about a blog post or anything else.

LeetCode Blind 75 - Part 2

Related Posts