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 Quesion: Maximum Product Subarray

Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Analysis:

Brutal force method will take O(n^2) time complexity, which is not acceptable.
Since it requires the "largest" product in an array, it is common to consider the DP(dynamic programming) method. And also since O(n^2) is NOT acceptable, there might be an O(n) solution.

So, given a whole scan , how to find the maximum product?
Note that, we need to consider two cases:
(1) negative numbers
          Store the minimum product to handle the case that new element < 0. Because if current element < 0, the product of two negative numbers (new element, and minimum product before the new element) become positive.
(2) zeros
        When meets zero, current max and min product become 0, new search is needed from the next element.

Therefore,  we can write down to function to store both + and - products:

max_product = max{A[i]*min_product (when A[i]<0),  A[i]*max_product (when A[i]>0),  A[i] (when 0 occurs before A[i]) }.

min_product = min{A[i]*min_product,  A[i]*max_product,  A[i] }.

Because current sequence might start from any element, to get the final result, we also need to store the max product after each iteration "res = max(res, maxp);".

Code(C++):

class Solution {
public:
    int maxProduct(int A[], int n) {
        int res = A[0];
        int maxp = A[0];
        int minp = A[0];
        for (int i=1;i<n;i++){
            int tmpmax = maxp;
            int tmpmin = minp;
            maxp = max(max(tmpmax*A[i],tmpmin*A[i]),A[i]);
            minp = min(min(tmpmax*A[i],tmpmin*A[i]),A[i]);
            res = max(maxp,res);
        }
        return res;
    }
};

Code(Python):

class Solution:
    # @param A, a list of integers
    # @return an integer
    def maxProduct(self, A):
        res = A[0]
        minp = A[0]
        maxp = A[0]
        for a in A[1:]:
            tmp_maxp = maxp
            tmp_minp = minp
            maxp = max(max(tmp_maxp*a, tmp_minp*a), a)
            minp = min(min(tmp_maxp*a, tmp_minp*a), a)
            res = max(res, maxp)
        return res
            
        

leetcode Question: Find Minimum in Rotated Sorted Array II

Find Minimum in Rotated Sorted Array II

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.


Analysis:
The solution is similar to the previous question (here), only difference is we can 'skip' the duplicates before determining if the sub array is ordered.

Code(C++):

class Solution {
public:
    void bs(vector<int> &num, int st,int ed, int &res){
        if (st>ed){ return; }
        else {
            int mid = st+(ed-st)/2; //get middle index
            
            while (num[mid]==num[ed] && mid!=ed) {ed--;}
            while (num[mid]==num[st] && mid!=st) {st++;}
            if (num[mid]<num[ed] || mid==ed){  // right part ordered
                res = min(res,num[mid]); //get right part min
                bs(num,st,mid-1,res); //search left part
            } else {  //right part unordered
                res = min(res,num[st]); //get left part min
                bs(num, mid+1, ed,res); //serch right part
            }
        }
    }
    int findMin(vector<int> &num) {
        int n = num.size();
        int res = num[0];
        bs(num,0,n-1,res);
        return res;
    }
};

Code(Python):

class Solution:
    # @param num, a list of integer
    # @return an integer
    def bs(self, num, st, ed, res):
        if st > ed:
            return res
        else:
            mid = st + (ed - st)/2
            while num[mid]==num[ed] and mid!=ed:
                ed -= 1
            while num[mid]==num[st] and mid!=st:
                st += 1
            if num[mid] < num[ed] or mid == ed:
                res = min(res, num[mid])
                return self.bs(num, st, mid-1, res)
            else:
                res = min(res, num[st])
                return self.bs(num, mid+1, ed, res)
        
    def findMin(self, num):
        n = len(num)
        res = num[0]
        return self.bs(num, 0, n-1, res)

leetcode Question: Find Minimum in Rotated Sorted Array

Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

Analysis:

In a sorted array, the minimum is the first element. Now the array has been rotated, so we need to search the minimum element. Binary search is usually a efficient way dealing with such problems where the "sub" array has the similar structure of the "parent" array.

In this problem, there is only 1 rotation, so that there are only limited cases when we split the array using the mid-element:
 1. the right part is ordered (A[mid] < A[ed])
 2. the right  part is unordered (A[mid] > A[ed])
 Some might say that what about the left part of the array? Note that there is only 1 rotation, which indicates that if right part is unordered, the left part of array must be ordered.

Considering the above two cases, finding the minimum is now becoming a simple binary search with slight modifications. Details can be seen in the following code.

Code(C++):

class Solution {
public:
    void bs(vector<int> &num, int st,int ed, int &res){
        if (st>ed){ return; }
        else {
            int mid = st+(ed-st)/2; //get middle index
            if (num[mid]<num[ed]){  // right part ordered
                res = min(res,num[mid]); //get right part min
                bs(num,st,mid-1,res); //search left part
            } else {  //right part unordered
                res = min(res,num[st]); //get left part min
                bs(num, mid+1, ed,res); //search right part
            }
        }
    }
    int findMin(vector<int> &num) {
        int n = num.size();
        int res = num[0];
        bs(num,0,n-1,res);
        return res;
    }
};

Code(Python):

class Solution:
    # @param num, a list of integer
    # @return an integer
    def bs(self, num, st, ed, res):
        if st > ed:
            return res
        else:
            mid = st + (ed - st)/2
            if num[mid] < num[ed]:
                res = min(res, num[mid])
                return self.bs(num, st, mid-1, res)
            else:
                res = min(res, num[st])
                return self.bs(num, mid+1, ed, res)
        
    def findMin(self, num):
        n = len(num)
        res = num[0]
        return self.bs(num, 0, n-1, res)