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;
}

Lesson 2: MissingIntegers (Missing Integers)

The strategy for this question is to create another array,
and use it as a flag if the value is found or not.

Since we need to find the minimum positive value, we can simply
neglect the negative values. We can also neglect any integer larger
than N, since if we find such a value (larger than N), that means any value between 1 and N may be lacking for sure. 

If all the values between 1 and N is found, that means the minimum positive value lacking is N + 1.

This strategy gives the score of 100%.

--------------------------------
       the solution
--------------------------------

int solution(int A[], int N) 
{
    //prepare the flags
    int* flag = (int*)calloc(sizeof(int), N);
    
    //iterate the given array A.
    int i;
    for (i = 0; i < N; i++){
        //we can neglect the value below 1 or larger than N.
        if (A[i] <= 0 || A[i] > N){
            continue;
        }
        //turn on the flag. this is the zero-indexed array.
        //so give -1 as the offset.
        flag[A[i] - 1] = 1;
    }
    
    //if there is no positive integer lacking between 1 - N,
    //the answer should be N + 1.
    int ans = N + 1;
    //found the minimum integer that is not found in the array A.
    for (i = 0; i < N; i++){
        if (flag[i] == 0){
            //the answer is (the index + 1). (we have -1 offset).
            ans = i + 1;
            break;
        }
    }
    
    //free the allocated memory space.
    free(flag);
    
    return ans;
}

Lesson 2: MaxCounters (Max Counters)

This is an interesting question in that a straight-forward answer won't get 100% because of performance efficiency.

For instance, the simple implementation as below will get only the score of 77%

 


--------------------------------------------
A Simple Solution
--------------------------------------------
struct Results solution(int N, int A[], int M) 

{
    struct Results result;

    result.C = calloc(sizeof(int), N);
    result.L = N;

    int max = 0;
    
    int i, j;
    for (i = 0; i < M; i++){
        int op = A[i];
        //if the op is max counter.
        if (op == N + 1){
            for (j = 0; j < N; j++){
                result.C[j] = max;
            }
        }
        //if the op is increase(x)
        else {
            //op is beweetn 1 to N, but the index for the array C 
            //is between 0 and (N-1). Decrease op to adjust it.
            op--; 
            result.C[op]++;
            if (result.C[op] > max){
                max = result.C[op];
            }
        }
    }

    return result;
}


The problem in performance efficiency seems caused by the inefficient implementation regarding the 'max counter' operation,
as the above implementation always go through the whole array to update the values when a 'max counter' operation is given.


Let's use flags so to remember if the slot has not been applied any 'increase' operation since the last 'max counter' operation, to avoid updating the whole array every time a 'max counter' operation is issued.

In the below implementation, we simply clear the flag array and remember the current max value.

The code also checks if the slot is updated since the last 'max counter' operation when an 'increase' operation is issued to the slot. If it is updated, the code simply increment the value in the slot. If not, the code updated the slot with 'maxAtTheLastMaxCntOp'.

The score is increased to 88%. So we still need more optimization.

--------------------------------------------
A Better Solution (1)
--------------------------------------------

struct Results solution(int N, int A[], int M) 

{

    struct Results result;

    result.C = calloc(sizeof(int), N);

    result.L = N;

    int* flg = alloca(sizeof(int) * N);

    memset(flg, 0x00, sizeof(int) * N);

    

    int max = 0;

    int maxAtTheLastMaxCntOp = 0;

    

    int i;

    for (i = 0; i < M; i++){

        int op = A[i];

        //if the op is max counter.

        if (op == N + 1){

            maxAtTheLastMaxCntOp = max;

            memset(flg, 0x00, sizeof(int) * N);    

        }

        //if the op is increase(x)

        else {

            //op is beweetn 1 to N, but the index for the array C 

            //is between 0 and (N-1). Decrease op to adjust it.

            op--; 

            if (flg[op] == 1){

                result.C[op]++;

            }

            else {

                result.C[op] = maxAtTheLastMaxCntOp + 1;

                flg[op] = 1;                

            }

            

            if (result.C[op] > max){

                max = result.C[op];

            }

        }

    }

    

    //apply the 'max counter' operation

    //to the slot(s) where it should be applied. 

    int j;  

    for (j = 0; j < N; j++){

        if (flg[j] == 0){

            result.C[j] = maxAtTheLastMaxCntOp;

        }

    }

    return result;

}

So the flag strategy didn't work much for better performance efficiency. What can we do now? One may notice that it is enough to check if the current value of the slot before applying an 'increase' operation is alwa below the 'maxAtTheLastMaxCntOp' value,

since if any 'increase' operation is applied to the slot already, the value in the slot should be at least equal to the 'maxAtTheLastMaxCntOp' value.

In the below implementation, finally we get the score of 100%.

--------------------------------------------
A Better Solution (2)
--------------------------------------------
struct Results solution(int N, int A[], int M) 
{
    struct Results result;

    result.C = calloc(sizeof(int), N);
    result.L = N;
    
    int max = 0;
    int maxAtTheLastMaxCntOp = 0;
    
    int i;
    for (i = 0; i < M; i++){
        int op = A[i];
        //if the op is max counter.
        if (op == N + 1){
            maxAtTheLastMaxCntOp = max;
        }
        //if the op is increase(x)
        else {
            //op is beweetn 1 to N, but the index for the array C 
            //is between 0 and (N-1). Decrease op to adjust it.
            op--; 
            if (result.C[op] < maxAtTheLastMaxCntOp){
                result.C[op] = maxAtTheLastMaxCntOp + 1;
            }
            else {
                result.C[op]++;
            }     
            //update the max value if necessary.
            if (max < result.C[op]){
                max = result.C[op];
            }
        }
    }
    
    //apply the 'max counter' operation
    //to the slot(s) where it should be applied. 
    int j;  
    for (j = 0; j < N; j++){
        if (result.C[j] < maxAtTheLastMaxCntOp){
            result.C[j] = maxAtTheLastMaxCntOp;
        }
    }
    return result;
}

Lesson 2: FrogRiverOne (Frog River One)

What you need to do is to check the input ArrayA until leaves fall on all the positions from 1 to X. So the strategy is to use flags to check if any leave fell there. 

If the leaves fell on all the positions from 1 to X, the time T when the last leave fell on a certain position (between 1 to X) is the answer.

int solution(int X, int A[], int N) 
{
    //the array to store flags
    int B[X];

    //clear the flags.
    memset(B, 0x00, sizeof(B[0]) * X);
    
    //let leaves fall!
    int t;
    int cnt = 0;
    int ans = -1;
    for (t = 0; t < N; t++){
        //get the position where a leave fall at time T. 
        int p = A[t] - 1; //(the array B is from 0 to X-1)
        //if it is between 0 to X-1 and 
        //no leave has fallen onto the position before, count it.
        if (p < X && B[p] == 0){
            B[p] = 1;
            cnt++;
            //is the route filled with leaves?
            if (cnt == X){
                ans = t;
                break;
            }
        }
    }

    return ans;
}

Lesson 2: PermCheck (Perm Check)

The expected worst-case time complexity of O(N) is likely to suggest that 'possibly no nested loop' and the expected worst-case space complexity O(N) is likely to suggest that 'we can allocate the memory for the temporary working area (or areas), the size of which is propositional to N'.

========================================================================

Complexity:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage 

(not counting the storage required for input arguments).

========================================================================

The below code uses a simple 'bucket' strategy. We first allocate

the memory for an array B to store flags. In this array , Each element at the index 'i' is '1', if the number 'i' appears in the array A and otherwise '0'. 

So we put the flags into these buckets in the array B.

Then, we check the array B so that if we can find any '0', which means the lacking number in the expected permutation. If there is no '0' in the array B, it is a permutation.

The below code gives this test score.

================================================================================

int solution(int A[], int N) 

{

    int B[N];

    memset(B, 0x00, sizeof(B));

    int i;

    for (i = 0; i < N; i++){

        if (A[i] > N){

           return 0;

        }

        B[A[i] - 1] = 1;

    }

    

    for (i = 1; i < N; i++){

        if (B[i] == 0){

           return 0;

        }

    }

    

    return 1;

}

Lesson 1: PermMissingElem (Perm Missing Elem)

As the expected worst-case space complexity is O(1), this problem is made a bit harder.

The strategy is to computer the expected sum when there is no lacking first, then subtract the actual sum you obtain from it.

=================================================================================

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

=================================================================================

int solution(int A[], int N) 
{
    long sum = ((long)N + 1) * (N + 2) / 2;
    
    int i;

    for (i = 0; i < N; i++){
        sum -= A[i];
    }
    
    return sum;
}