Leetcode 191. Number of 1 Bits

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

For example, the 32-bit integer ’11′ has binary representation 00000000000000000000000000001011, so the function should return 3.

Analysis:

We need to check each bit of the integer. To do that, we have a mask and let mask start from 1, which is 0000 0000 0000 0000 0000 0000 0000 0001, then use a logical AND between the number  and the mask. If the result is not 0, then that means the digit is 1. Then we shift the mask to left by one.

Time complexity: O(1)

Space complexity: O(1)

Code is below:

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        // O(1)
        
        int count = 0;
        int mask = 1;
        
        // Have a mask from 1, 0000 0000 0000 0000 0000 0000 0000 0001
        // Use logial AND to check it
        // Shift the mask left by 1
        for (int i = 0; i < 32; i++) {
            if ((n & mask) != 0) {
                count++;
            }
            mask <<= 1;
        }
        
        return count;
    }
}

Leetcode 268. Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Analysis:

Basically, we can use the same method of single number. To go through the whole array, use two xors to get the missing number.

Time complexity: O(n)

Space complexity: O(1)

The code is below:

public class Solution {
    public int missingNumber(int[] nums) {
        // O(n) O(1)
        // 0 ^ a = a， a ^ b ^ a = b

if (nums == null || nums.length == 0) {
return 0;
}

int result = nums.length;
for (int i = 0; i < nums.length; i++) {
// xor 0-n
result ^= i;
// xor nums[0] – nums[n]
// result = missing
result ^= nums[i];
}

return result;
}
}

Leetcode 136. Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Analysis:

Bit manipulation. Based on the rules that a ^ b ^ a = b,  0 ^ b = b. So we can go through the whole array and use the xor to get the only one.

Time complexity: O(n)

Space complexity: O(1)

Below is the code:

public class Solution {
    public int singleNumber(int[] nums) {
        // O(n) O(1)
        // a ^ b ^ a = b,  0 ^ b = b
        
        // Corner case
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            result ^= nums[i];
        }
        
        return result;
    }
}