Lesson 4: MaxProductOfThree (Max Product of Three)

The trick is to produce a max product, we have to consider any two of the three picked up values can be negative. In this case, the product of these two negative values can be positive.

So what we need to do is to compute the product of two smallest values and one biggest values and the product of three biggest values.

The bigger one of these two will be the maximum product.

This is indeed a O(N) time complexity problem,
as we don't even have to sort the array. We just have to obtain two minimum values and three biggest values for this strategy.

--------------------------------
SOLUTION
--------------------------------
int solution(int A[], int N) 
{
    if (N == 3){
        return A[0] * A[1] * A[2];
    }
    int max1 = -1001;  
    int max2 = -1001;    
    int max3 = -1001;   
    
    int min1 = 1001;   
    int min2 = 1001;      
    int i;        
    for (i = 0; i < N; i++){
        int tmp = A[i];
        if (tmp > max1){
            max3 = max2;
            max2 = max1;
            max1 = tmp;
        }     
        else if (tmp > max2){
            max3 = max2;
            max2 = tmp;
        }         
        else if (tmp > max3){
            max3 = tmp;
        }
        
        if (tmp < min1){  
            min2 = min1;   
            min1 = tmp;    
        }      
        else if (tmp < min2){
            min2 = tmp;
        }   
    }        
    
    int val1 = max1 * max2 * max3;    
    int val2 = max1 * min1 * min2;  
    
    return val1 > val2 ? val1 : val2;
}

Lesson 4: Distinct (Distinct)

This is a simple problem.


First, we sort all the values, and then scan if there is any slot, the value of which is different from its previous slot.

Possibly, a bug can be caused if you forget to check corner cases: if N == 0 or N == 1, so we should return 0 or return 1, respectively.

int comparator(const void *a, const void *b)
{
    if (*(int*)a == *(int*)b){
        return 0;
    }
    
    if (*(int*)a < *(int*)b){
        return -1;
    }
    
    
    return 1;
}

int solution(int A[], int N) 
{
    if (N == 0){
        return 0;
    }
    
    qsort(A, N, sizeof(int), comparator);
    
    int cnt = 1;
    
    int i;    
    for (i = 1; i < N; i++){
        if (A[i - 1] != A[i]){
            cnt++;
        }
    }
    
    return cnt;
}

Lesson 4: Triangle (Triangle)

This is another math question.

First, let's sort the array in ascending order.

Then, we can have A[P] <= A[Q] <= A[R] for any 0 <= P < Q < R < N, as it is sorted in ascending order.

Then, assume all of these are positive values:
(0 <  A[P] <=  A[Q] <= A[R]).

Because the values are sorted, we can say as follows.
The condition 'A[P] < A[Q] + A[R]' always holds.
The condition 'A[Q] < A[P] + A[R]' also always holds, as 0 <= A[Q] <= A[R].

The condition 'A[R] < A[P] + A[Q]' needs to be checked., yet if we have a certain value R for A[R], we only have to check the two slots right before A[R], each of which as A[P] or A[Q] respectively, is bigger than A[R]. (We only have to if there is any triangular exist or not. as these two values are biggest, we only have to see these two.)

The reason why we can neglect any negative value is as follows.

If A[P] <= 0 <= A[Q] <= A[R], A[P] + A[Q] <= A[Q]. 
Then, it will be always `A[P] + A[Q] <= A[Q] <= A[R]', thus, 'A[R] < A[P] + A[Q]' is violated.

Thus, after sorting we only have check three consecutive slots from the head to the tail in the array A.


This strategy can give the score of 100%. While it would be better to use merge sort to guarantee the time complexity O(N log (N)), I used quick sort instead to simplify the implementation, since I don't think I need to bother myself to implement merge sort.

This question also requires us to avoid both overflow and underflow.

People often write like 'return *(int*)a - *(int*)b;' for the comparator function for C's qsort library function, this can cause underflow. Writing 'r < p + q' may cause overflow when p + q are large. These were good lessons for me...

int compare_int(const void *a, const void *b)
{
   //don't do 'return *(int*)a - *(int*)b;',
   //as this can cause underflow or overflow.

   if (*(int*)a == *(int*)b){
       return 0;
   }

   if (*(int*)a < *(int*)b){
       return -1;
   }
   
   return 1;
}

int solution(int A[], int N) 
{
    if (N < 3){
        return 0;
    }
    
    qsort(A, N, sizeof(int), compare_int);
    
    int i;
    for (i = 2; i < N; i++){
        
        int p = A[i - 2];
        int q = A[i - 1];
        int r = A[i];
        
        //neglect negative values.
        if (p <= 0){
            continue;
        }

        //if write like 'r < p + q', 'p + q' may overflow.
        if (r - p < q ){
            return 1;
        }
    }
    
    return 0;
}

Lesson 3: CountDiv (Cound Div)

This is another simple math question.

See the figure above.

When A % K == 0, the answer can be given by (B - A) / K + 1.
When A % K != 0, the answer can be given by (B - (A - A % K)) / K.

----------------------------------------
SOLUTION
----------------------------------------
int solution(int A, int B, int K) 
{
    if (A % K == 0){
        return (B - A) / K + 1;
    }

    return (B - (A - A % K)) / K;
}

Lesson 3: MinAvgTwoSlice (Min Avg Two Slice)

This problem is indeed a math question. 

To check the number of the slots that produce the minimum average, we only have to check the sum of the consecutive two or three slots.

Think of the case in which there are the slice made of four slots. Let's assume these four slots can produce the minimum average. 

The slice can be decomposed into two pairs, each of which consists two slots. If any of these pairs can produce a smaller average than the original four slots, then it contradicts the first assumption. If they produce a bigger average, then the other pair must be smaller than the average of the original four slots. So will be the same value. The same can be said to 5 slots (2+3), etc.

This can be said to any slice of an arbitrary size. If any sub-slice of a certain slice can produce a smaller average, then the original slice is not the slice that can produce a smaller portion. It the average values of the original slice and sub-slice are the same, we can simply take the index where the original slice starts, since what we need to return is the smallest index.

The below code implements this strategy and returns the score of 100%.

int solution(int A[], int N) 
{
    int i = 0;
    
    if (N == 2){
        return 0;
    }

    //initialize the current minimum average of the first two slots.
    double minavg = (A[0] + A[1]) / 2.0;
    int idx = 0;
    

    for (i = 2; i < N; i++){
        double tmp1 = (A[i - 1] + A[i]) / 2.0;
        double tmp2 = (A[i - 2] + A[i - 1] + A[i]) / 3.0;
        
        if (tmp1 < minavg){
            idx = i - 1;
            minavg = tmp1;
        }
        if (tmp2 < minavg){
            idx = i - 2;
            minavg = tmp2;
        }
    }
    return idx;
}

Lesson 3: GenomicRangeQuery (Genomic Range Query)

This is another 'running total' problem.

The strategy is to scan the string S once to memorize
each running total of ACGT at the position.

For instance, if the totals of ACGT  are [4,2,3,1] at the index 'p' and [4,5,5,1] at the index 'q' (p <= q), we can say that there is no A and T found between p and q, because the total numbers of A and T stay the same. On the other hand, we can say there are C and D, the total numbers of C and G are increased.

The code below implements this strategy. We allocate the N + 1 size array so that we can simplify the code.

The code gives the score of 100%.

--------------------------------
SOLUTION
--------------------------------
struct Results solution(char *S, int P[], int Q[], int M) 
{
    typedef struct ACGT {
        int a;
        int c;
        int g;
        int t;
    } ACGT;
    
    int N = strlen(S);
    ACGT* acgt = calloc(sizeof(ACGT), (N + 1));
    
    int i;
    int a = 0;
    int c = 0;
    int g = 0;
    int t = 0;

    //count the numbers of ACGT. 
    for (i = 0; i < N; i++){
        switch(S[i]){
            case 'A':
                a++;
                break;
            case 'C':
                c++;
                break;
            case 'G':
                g++;
                break;
            case 'T':
                t++;
                break;
            default:
                exit(-1);
        }
        //we leave acgt[0] untouched (filled with zero)
        //so that we can simplify the next step.
        acgt[i + 1].a = a;
        acgt[i + 1].c = c;
        acgt[i + 1].g = g;
        acgt[i + 1].t = t;
    }
    
    
    struct Results result;
    
    result.A = calloc(sizeof(int), M);
    result.M = M;
    
    for (i = 0; i < M; i++){
        ACGT s = acgt[P[i]];
        ACGT e = acgt[Q[i] + 1];
        if (e.a - s.a > 0){
            result.A[i] = 1;
        }
        else if (e.c - s.c > 0){
            result.A[i] = 2;
        }
        else if (e.g - s.g > 0){
            result.A[i] = 3;
        }
        else {
            result.A[i] = 4;
        }
    }
    
    
    free(acgt);
    
    return result;
}

Lesson 3: PassingCars (Passing Cars)

Note that each car traveling west will meet all the cars traveling east, which is coming form the opposite direction.

So in the following code, what it does is to count the number of cars traveling east from the head of the array, and when a car traveling west is found to then add the current value of the counter to cars traveling west to the counter of passing cars.

This strategy gives the score, 100%.

int solution(int A[], int N) 
{
    int cnt = 0;
    int cntCarsTravelingEast = 0;
    
    int i;
    for (i = 0; i < N; i++){
        if (A[i] == 0){
            cntCarsTravelingEast++;
        }
        else {
            cnt += cntCarsTravelingEast;             
            if (cnt > 1000000000){
                return -1;
            }
        }
    }
    
    return cnt;
}