260. Single Number III

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

Solution:
Do not have any clue for this question with time complexity of O(n) and space complexity of O(1). Thought about bitwise operation, but still cannot figure out how to distinguish two different numbers until searching online. The reference link is listed below.

First step is to obtain the xor of the two different nums, which is trivial; then is the key part: choose one non-zero bit of the xor result as an indicator to separate the initial nums into two groups. Each group should have one of two unique elements. Then it is trivial to find them.

Code:

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> res(2, 0);
        int t = 0; 
        for(auto a:nums) t ^= a;
        t &= -t; //the most-right non-zero bit;
        for(auto a: nums){
            if(t&a) res[0] ^=a;
            else res[1] ^=a;
        }
        return res;
    }
};

http://www.cnblogs.com/grandyang/p/4741122.html

201. Bitwise AND of Numbers Range

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

Solution:

We need to find a way to reduce the time complexity. As indicated by the title, bitwise operation may be a choice. One way is to check the 1s and 0s at each bit (31 bits in total). For each bit, once 0 is found, then the final results at that bit will be 0 (bitwise AND).

But this still is not enough. Actually once the number on the higher edge has one bit that is 1 on the higher bits more than that of the lower edge, then all the bits will become 0 from AND. So we just need to find the locations of the highest bit that is 1 for both m and n. If the location of n is higher than that of m, the result will be 0. (we can also work on the lower side to figure out the highest location for the non-zero bits for both numbers, then the iteration can start from that bit to higher once. But for simplicity, I just set the out-layer loop starting from 0.)

One detail, when n is the INT_MAX, we cannot use it as the end condition for the for-loop (since it will trigger INT_MAX + 1). However, the good new is that INT_MAX itself has no constrain on AND at all. So once n is the maximum, we just need to set it to be INT_MAX - 1.

Code:

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        if(n==INT_MAX) n = n-1;
        int res = 0;
        int l1 = 30, l2 = l1;// l1 is the highest "1" bit location for m; 
        while(l1>=0){
            if((1<<l1)&m) break;
            --l1;
        }
        while(l2>=0){// similar for l2 to n;
        if((1<<l2)&n) break;
            --l2;
        }
        if(l2>l1) return 0;
        for(int i=0; i<=l1; ++i){
            int t = (1<<i);
            for(int j=m; j<=n; ++j){
                t = t & j;
                if(!t) break;
            }
            res |= t;
        }
        return res;
    }
};  

187. Repeated DNA Sequences

https://leetcode.com/problems/repeated-dna-sequences/

Solution:

It is straightforward to use the "brute force" hash map method plus a sliding window with size of 10-letter. But something else can be applied to reduce the space complexity since it is too expensive when using string as the hash key.

We just need to distinguish four letters, so bitwise operation may be used and two bits are enough for four, i.e. 'A' can be 00, 'C' for 01, 'G' for 10, and 'T' for 11.

Two details need to consider:

1) : a mask may need to set all the bits beyond the first 20 from the left to be 0. (since we only need to consider the "10-letter" sub-sequences and each letter need 2 bits). 0xFFFFF represents the first 20 bits from the left are 1s, and all the rest are 0s. (F in hexadecimal is equivalent to 1111 in binary);

2): need to remove the possible duplicates. Can use set, but actually can also use hash map, see below.

Code:

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> res;
        unordered_map<char, int> m1{{'A', 0}, {'C', 1}, {'G', 2}, {'T', 3}};
        unordered_map<int, int> m2;
        int i = 0, t = 0, mask = 0xfffff;  // the lower 20 bits are 1s;
        while(i<9) t = (t<<2) + m1[s[i++]];
        while(i<s.size()){
            t = ((t<<2) & mask) | m1[s[i++]];
            if(m2.find(t) == m2.end()) m2[t] = 1;
            else{ 
                if(m2[t] == 1){
                    res.push_back(s.substr(i-10, 10));
                    m2[t] = 0;
                }
            }
        }
        return res;
    }
};

477. Total Hamming Distance

https://leetcode.com/contest/leetcode-weekly-contest-13/problems/total-hamming-distance/

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Solution:
May use the bitwise operation to reduce the time complexity. All the numbers can be viewed as 32 bits with 0s and 1s. So for each bit, we just need to count the total number of 1s, then the total number of 0s will be (total numbers - the numbers of 1s). And the contribution to the Hamming distance will be count of 1s times the count of 0s. Similar argument can be applied to all the rest bits.

Code:

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int res = 0;
        for(int i=0; i<32; ++i){
            int one = 0;
            for(int j=0; j<nums.size(); ++j){
                if((1<<i) & nums[j]) ++one;//one is the numbers of 1s;
            }
            res += one*(nums.size()-one);// nums of 1s x nums of 0s
        }
        return res;
    }
};