leetcode Question: Single Number III

Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

1. The order of the result is not important. So in the above example, [5, 3] is also correct.
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Analysis:

From the previous questions we know that the bit manipulation would be a good start to go, same as this problem. The hard part is by XOR all the values in the array, we only have the XOR of the two numbers we have, say  x = a^b. 

From the figure I draw below, it is easy to see that:   the essential usage of XOR operation is to check whether the corresponding bits are same or not between two numbers. In other words, if there is any one bit between the two numbers is set to ‘1’  (e.g., any one bit in x is '1’), the two numbers (e.g., a and b) are impossible to be the same.

Let’s extend the above conclusion to this problem:

1. We have a serise of numbers. 
   
2. We have value x = a ^ b, but we don’t know which two numbers are a and b.
   
3. But we know, there must be at least one bit in a and b are NOT the same. (because x is NOT 0, there must be at least one bit in x is 1)
   
4. In other words, in a certain bit, say kth bit, a must be 0 and b must be 1, or vice versa.
5. Look at the array, every number in the array may be a, or b.
   
6. For every number in the array，look at the kth bit , it has only two possible values: 0 or 1.
7. So if we divide the number in the arrary simplely by the kth bit, the array is divided into two part, and a and b must be in different part.
8. For each part, except the number a (or b), all the other numbers must appear twice in the same part.
9. Now the problem becomes the simple version of single number we have seen before.
10. Done.

Therefore, we have successfully transit the problem into two sub problems, in which a simple loop with XOR operations will work well to solve.

Code (C++):

class Solution {

public:

vector<int> singleNumber(vector<int>& nums) {

vector<int> result(2,0);

int xor_res = 0;

for (int i = 0; i < nums.size();++i){

xor_res ^= nums[i];

}

int mask = xor_res ^ ( xor_res & (xor_res-1) );

int p=0;

int q=0;

for (int i=0;i<nums.size();++i){

if ( (nums[i] & mask) == 0){

p ^= nums[i];

}else{

q ^= nums[i];

}

}

result[0] = p;

result[1] = q;

return result;

}

};

Code (Python):

class Solution(object):

def singleNumber(self, nums):

"""

:type nums: List[int]

:rtype: List[int]

"""

r = 0

for num in nums:

r ^= num

mask = r ^ ( r & (r-1) )

p = 0

q = 0

for num in nums:

if (num & mask) == 0:

p ^= num

else:

q ^= num

return [p ,q]

leetcode Question: Missing Number

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:

First let's take a look at the requirement in the "Note" and review the runtime complexity.  It is required linear. According to https://en.wikipedia.org/wiki/Time_complexity, linear time  == O(n).  Usually, for such problem given an array, O(n) algorithm have constant time of for loop. For this problem, only one loop from the start to the end should be enough to solve it.

Think about what we have at hand right now:

• an array of numbers, the length is n.
• a for loop, with an index int i  i = 0 to n-1
• The array is NOT sorted!

Since the array should be continuous but now missed one number,  the index i could be used as a reference, by check the i and the values in array, we don't have to open another spaces to store the array from 0 to n.  However, index i changes every iteration, and the array is not sorted, how can we save the previous values using only constant extra space?

For this problem, if it reminds you the bit manipulation, I think this problem surprisingly becomes very easy. If you have not idea what bit manipulation is, let's now take a brief review of one bit operation: XOR.

From the figure below, I show the XOR operation between 0 and 1 in binary. Basically, XOR checks if the two bits are same (return 0 ) or not (return 1).  For two numbers in decimal, the XOR can be used to check if they are the same,  and return 0.  Also, the XOR between any number and 0 results in the number itself.  Besides, for more than two decimal numbers, the XOR of all those numbers is not related to the order.

Therefore, by check the figure I drawn below, this problem can be solved pretty straightforward by O(n) time, and O(1) space.

    

Code(C++):

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

Code(Python):

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = 0
        c = 0
        for x in nums:
            res = res ^ c ^ x
            c += 1
        return res ^ c

leetcode Question: Power of Two

Power of Two

Given an integer, write a function to determine if it is a power of two.

Analysis:

An straightforward way is to keep doing "divide by 2" for the number and check if current number "mod 2" is zero. However this is pretty slow (it still can pass the OJ).

More efficient way is to use bit manipulation.

If one number is a power of 2, then its binary must starts with 1 and all the lower bits are 0. e.g.,
2 10
4 100
8 1000
16 10000
...

Also, we have to find a "mask" to check this format, what "mask" should we use?
Let's see some examples:
1 01
3 011
7 0111
15 01111
...

Well, it is not hard to see that,  if one number "n" is a power of 2, then "n-1" must have all 1s in its binary format. Therefore, "n & n-1" must be 0.  

Code(C++):

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return ( (n>0) && (n & (n-1))==0 ) || (n==1);
    }
};

Code(Python):

aclass Solution(object):
    def isPowerOfTwo(self, n):
        """
        :type n: int
        :rtype: bool
        """
        return n>0 and  n & (n-1)==0 or n==1

leetcode Question: Bitwise AND of Numbers Range

Bitwise AND of Numbers Range

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

Analysis:

At the first glance, looping from m to n seems straightforward but obviously time-consuming.
Looping from number to number seems unavailable, but we can considering looping from bit to bit.
Let's first write down some binary numbers:

1    000001
2    000010
3    000011
4    000100
5    000101
6    000110
7    000111
8    001000

Let's consider each bit from low to high, we can observe that the lowest bit, is either 1 or 0 after a number of AND operation. In this problem, because the range is continuous, the only case that lowest bit will become 1 is when m==n, and the lowest bit is 1. In other words,  for the range [m, n], if n > m, the lowest bit is always 0. Why? Because either the lowest bit of m is 0 or 1, the lowest bit of (m AND m+1) must be 0.

Now we have get the lowest bit for final result, next step is to check the 2nd lowest bit. How to do it? Just using bit shifting!  m >> 1 and n >> 1 is all we need.

When to stop looping? Consider the case that:
m =  01000
n =   01011

(1)   01011 > 01000  ->  lowest bit = 0
(2)   0101 > 0100      ->  2nd lowest bit  = 0
(3)   010 = 010          ->  3rd lowest bit = current lowest bit  0
(4)   01 = 01              ->  4th lowest bit = current lowest bit   1
(5)   0 = 0                  ->  5th lowest bit = current lowest bit   0

Final result:   01000
We can see that step (3)-(5) is unnecessary, when m=n, the other bits are just the same as current m (or n), then we can easily get the final result.

The code below are writing in two fashions: using loop and recursion. The former is easy understand, while the later is neat and simple.

Loop:
Code(C++):

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

Code(Python):

class Solution:
    # @param {integer} m
    # @param {integer} n
    # @return {integer}
    def rangeBitwiseAnd(self, m, n):
        k = 0
        while True:
            if n > m:
                k += 1
            else:
                return m<<k
            m = m >> 1
            n = n >> 1
            
                
        

Recursive:
Code(C++):

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
       if (n>m){
           return rangeBitwiseAnd(m>>1, n>>1)<<1;
       }else{
           return m;
       }
    }
};

Code(Python):

class Solution:
    # @param {integer} m
    # @param {integer} n
    # @return {integer}
    def rangeBitwiseAnd(self, m, n):
        if n > m:
            return self.rangeBitwiseAnd(m>>1, n>>1) << 1
        else:
            return m
                
        

leetcode Questions: Reverse Bits

Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?

Analysis:

This is a very basic bit manipulation problem.

Some experience about the basic bit operation (not the STL in C++):
1. mask is a very good tool
2. bit shifting operations (<<, >>) are very inportant
3. loop is usually enough
4. be careful with the data type.


In this problem, the first task is to get the binary bits from uint number n.
Let's say n = 43261596,  the binary format is: 00000010100101000001111010011100
In order to get the binary bits, mask is used here.
The idea of using mask to check 1 bit each time, using AND operation.

Mask moves 1 bit each time using << operation.
Mask can be computed and saved before to speed up the reverse function.

E.g.
iteration 1:  mask = 0000...00001,  then mask & n  = 0
iteration 2:  mask = 0000...00010, then mask & n  = 0
iteration 3:  mask = 0000...00100,  then mask & n  = 1
iteration 4:  mask = 0000...01000, then mask & n  = 1
...
iteration 32:  mask = 1000...00000, then mask & n  = 0

In this way, binary bits can be obtained from 32 iterations.
Reverse thus becomes pretty easy when using this looping.


The next step is to convert bits back into integer. Bit shift is all we need. "<< " shifts 1 bit left. (Remember if you shift left on an unsigned int by K bits, this is equivalent to multiplying by 2^K.)
In this problem, we check the original int from the lowest bit to highest, so the first bit in the original int is the highest bit in the result int. By shifting the final int 1 bit each time, the final int after 31 (32-1) times shifting, it becomes the reverse int of the original int.  32 is the length of the int data type in this problem.

Code(C++):

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t res = 0;
        uint32_t mask = 1;
        for (int i=0;i<32;i++){
            if (n&mask) res = res + 1;
            if (i!=31) res <<= 1;
            mask <<= 1;
        }
        return res;
    }
};

Code(Python):

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        res = 0
        mask = 1
        for i in range(0,32):
            if n & mask:
                res += 1
            if i != 31:
                res <<= 1
            mask <<= 1
        return res
        

leetcode Question: Number of 1 Bits

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:

This is a very basic bit manipulation problem.
In order to count the number of 1 in the bit string, we can use a mask to check if the last bit is 1 or 0.
Cut the last bit (shift 1 bit right) and iterate this operation can achieve the final task.

mask = 1, binary of which is 0000...000001 (length meets with uint32)
shift operation:   >>1.

Note that << shifts left and adds 0s at the right end
>> shifts right and adds 0s at the left (when data is unsigned int)

Code(C++):

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

Code(Python):

class Solution:
    # @param n, an integer
    # @return an integer
    def hammingWeight(self, n):
        res = 0
        while n:
            if n&1:
                res += 1
            n = n >> 1
        return res
        
        

leetcode Question: Single Number II

Single Number II

Given an array of integers, every element appears three times 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:

The general idea of this problem, is to consider all the numbers bit by bit, count the occurrence of '1' in each bit. To get the result, check if the number can be divided by 3 (mod 3 = 0), put '0' if true and '1' otherwise.

(Idea coming from the internet)
Since we know that XOR operation can be used for testing if 1 bit occurs twice, in other words, for a single bit, if 1 occurs twice, it turns to 0.
Now we need a 3-time criteria for each bit, by utilizing the bit operations.
This 3-time criteria needs every bit turns to 0 if  '1' occurs three times.

If we know on which bits '1' occurs twice, and also know on which bits '1' occurs 1-time, a simple '&' operation would result in the bit where '1' occurs three times. Then we turn these bit to zero, would do well for this problem.

(1). Check bits which have 1-time '1', use the XOR operation.
(2). Check bits which have 2-times '1's, use current 1-time result & current number.
(3). Check bits which have 3-times '1's, use '1-time' result & '2-times' result
(4). To turn 3-times bits into 0:   ~(3-times result) & 1-time result
                                                     ~(3-times result) & 2-times result
   
E.g.,We have numbers:  101101,   001100, 101010
To count the occurrence of 1's:
101101
001100
101010
count:  {2,0,3,2,1,1}

Denote:
t1: bit=1 if current bit has 1-time '1'
t2: bit=1 if current bit  has 2-times '1'
t3: bit=1 if current bit  has 3-times '1'

Result:
t1 = 000011, t2 = 100100, t3 = 001000



Initialization: t1 = 000000, t2=000000, t3 = 000000
(1) 101101
t1 = 101101  (using XOR)
t2 = 000000
t3 = 000000

(2)001100
% Current 2 times bits (t2) and NEW 2 times bits coming from 1 time bits and new number.
t2 = t2 | 001100 & t1 =  001100 & 101101 = 001100
t1 = t1 XOR 001100 = 100001
t3 = t2 & t1 = 000000

(3)101010
t2 = t2 | (101010 & t1) = t2 | (101010 & 100001) = 101100
t1 = t1 XOR 101010 = 100001 XOR 101010 = 001011

t3 = t1 & t2 = 001000

%Turn 3-time bits into zeros
t1 = t1 & ~t3 = 000011
t2 = t2 & ~t3 = 100100

Code(C++):

class Solution {
public:
    int singleNumber(int A[], int n) {
        int t1 = 0;
        int t2 = 0;
        int t3 = 0;
        
        for (int i = 0; i < n; i++){
            t1 = t1 ^ A[i];
            t2 = t2 | ((t1^A[i]) & A[i]);
            t3 = ~(t1 & t2);
            t1 = t1 & t3;
            t2 = t2 & t3;
        }
        
        return t1;
        
    }
};

Code(Python):

class Solution:
    # @param A, a list of integer
    # @return an integer
    def singleNumber(self, A):
        t1 = 0;
        t2 = 0;
        t3 = 0;
        for a in A:
            t2 = t2 | (t1 & a);
            t1 = t1 ^ a;
            t3 = ~(t1 & t2);
            t1 = t1 & t3;
            t2 = t2 & t3;
        return t1;

leetcode Question: Single Number I

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:

The requirement is O(n) time and O(1) space.
Thus, the  "first sort and then find " way is not working.
Also the "hash map" way is not working.

Since we can not sort the array, we shall find a cumulative way, which is not about the ordering.

XOR is a good way, we can use the property that A XOR A = 0, and A XOR B XOR A = B.

So, the code becomes extremely easy.

Code(C++):

class Solution {
public:
    int singleNumber(int A[], int n) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        int res = A[0];
        for (int i=1;i<n;i++){
            res = res ^ A[i];
        }
        return res;
    }
};

Code (Python):

class Solution:
    # @param A, a list of integer
    # @return an integer
    def singleNumber(self, A):
        res = 0
        for a in A:
            res = res ^ a
        return res

leetcode Question 104: Subsets

Subsets:

Given a set of distinct integers, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Analysis:

The easiest idea is using the binary numbers.
e.g.
set [a,b,c], write the binary numbers of length 3.

000    []
001    [a]
010    [b]
011    [ab]
100    [c]
101    [ac]
110    [bc]
111    [abc]

Then the problem is pretty easy, for each number in binary format,  check which bit is 1 or 0, we just add the ith number into the set if the ith bit in the number is 1.

Bit manipulation is enough for the check, we just have to shift the number 1 one bit left each time, a simple AND operation will give us the bit value.

Code(C++):

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        vector< vector<int> > res;
        if (n == 0){ return res;}
        
        for (int i=0;i< pow(2,n); i++){
            vector<int> tmp;
            for (int j=0;j<n;j++){
                if ( (i& (1<<j)) > 0 ){
                    tmp.push_back(nums[j]);
                }
            }
            res.push_back(tmp);
        }
        return res;
    }
};

Code (Python):

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        n = len(nums)
        if n==0:
            return res
        
        for i in range(pow(2, n)):
            l = []
            for j in range(n):
                if i & (1 << j) > 0:
                    l.append(nums[j])
            res.append(l)
        return res