Triangle 100% Solution in Javascript

Question

app.codility.com

My Solution

app.codility.com

function solution(A) {

    if (A.length < 3)
        return 0;
        
    A.sort((a, b)=>(a - b));

    for (let i = 2; i < A.length; i++) {
        if (A[i] < A[i-1] + A[i-2]) {
            return 1;
        }
    }
    
    return 0;

}

MaxProductOfThree 100% Solution in Javascript

Question

app.codility.com

My Solution I (O(NlogN))

app.codility.com

function solution(A) {
    
    A.sort((a, b)=>(a - b));
    
    // 2 types (--+) or (+++)
    
    let type1 = A[0]*A[1]*A[A.length-1];
    let type2 = A[A.length-1]*A[A.length-2]*A[A.length-3];
    
    return Math.max(type1, type2);
    
}

My Solution II (O(N))

without sorting, finding max and min five times

app.codility.com

function solution(A) {
    
    // 2 types (--+) (+++)
    // try to do without sorting
    
    let max = [-1001, -1001, -1001];
    let index = [-1, -1, -1];
    
    for (let i = 0; i < 3; i++) {
        for (let j = 0; j < A.length; j++) {
            if (A[j] > max[i] && j != index[(i+1)%3] && j != index[(i+2)%3]) {
                max[i] = A[j];
                index[i] = j;
            } 
        }   
    }
    
    let min = [1001, 1001];
    let index2 = [-1, -1];

    for (let i = 0; i < 2; i++) {
        for (let j = 0; j < A.length; j++) {
            if (A[j] < min[i] && j != index2[(i+1)%2]) {
                min[i] = A[j];
                index2[i] = j;
            }
        }
    }

    return Math.max(max[0]*max[1]*max[2], max[0]*min[0]*min[1]);

}

My Solution III O(N)

without sorting, finding max and min five times The same concept of the above, but running 2N rather than 5N

app.codility.com

function solution(A) {
    
    let max3 = [A[0], A[1], A[2]];
    max3.sort((a, b)=>(a - b));
    
    for (let i = 3; i < A.length; i++) {
        if (A[i] > max3[0]) {
            max3[0] = A[i];
            max3.sort((a, b)=>(a - b));
        }   
    }
    
    // console.log(max3);
    
    let min2 = [A[0], A[1]];
    min2.sort((a, b)=>(b - a));
    // console.log(min2);
    
    for (let i = 2; i < A.length; i++) {
        if (A[i] < min2[0]) {
            min2[0] = A[i];
            min2.sort((a, b)=>(b - a));
        }
    }
    
    // console.log(min2);
    
    return Math.max(max3[0]*max3[1]*max3[2], min2[0]*min2[1]*max3[2]);
    
}

Distinct 100% Solution in Javascript

Question

app.codility.com

My Solution

app.codility.com

function solution(A) {
    
    if (A.length === 0 || A.length === 1)
        return A.length;
    
    A.sort((a, b)=>(a - b));
    
    let cur = A[0];
    let count = 1;
    
    for (let i = 0; i < A.length; i++) {
        if (A[i] != cur) {
            cur = A[i];
            count++;
        }
    }
    
    return count;

}

CountDiv 100% Solution inJavascript

Question

app.codility.com

My Solution (O(1))

app.codility.com

function solution(A, B, K) {
    
    // find the smallest multiple of K (A or above)
    let minKsMult = Math.ceil(A/K)*K;
    
    // there's none
    if (minKsMult > B)  
        return 0;
    else
        return Math.floor(B/K)-Math.ceil(A/K)+1;
    
}

MinAvgTwoSlice 100% Solution in Javascript

Question

app.codility.com

My Solution

This is the most challenging one I've ever seen in codility (if you also start from Q1 to here), the trick is that any slices of arbitrary length can be broken into sub-slices of length 2 or 3. The proof is in the below link codesays.com

app.codility.com

function solution(A) {
    
    let prefixSum = [];
    prefixSum[0] = 0;
    
    for (let  i = 1; i <= A.length; i++) {
        prefixSum[i] = prefixSum[i-1] + A[i-1];
    }
    
    let min = 10001;
    let startIndex = 0;
    
    // for slices with length 2
    for (let i = 0; i < prefixSum.length-2; i++) {
        
        let avg2 = (prefixSum[i+2] - prefixSum[i])/2;
        
        if (min > avg2) {
            min = avg2;
            startIndex = i;
            // console.log(min+", "+startIndex);
        }
    }
    
    // for slices with length 3
    for (let i = 0; i < prefixSum.length-3; i++) {
        
        let avg3 = (prefixSum[i+3] - prefixSum[i])/3;    
        
        if (min > avg3) {
            min = avg3;
            startIndex = i;
            // console.log(min+", "+startIndex);
        }
        
    }
    
    return startIndex;
    
}

GenomicRangeQuery 100% Solution in Javascript

Question

app.codility.com

My Solution

app.codility.com

function solution(S, P, Q) {
    
    let prefixASum = [];
    let prefixCSum = [];
    let prefixGSum = [];
    let prefixTSum = [];
    let ASum = 0;
    let CSum = 0;
    let GSum = 0;
    let TSum = 0;
    
    let ans = [];
    
    for (let i = 0; i <= S.length; i++) {
        
        if (i > 0) { // prefix[0] = 0
            switch (S[i-1]) { // prefix[1] = a0
                case 'A':
                    ASum++;
                    break;
                case 'C':
                    CSum++;
                    break;
                case 'G':
                    GSum++;
                    break;
                case 'T':
                    TSum++;
                    break;
            }
        }
        
        prefixASum[i] = ASum; 
        prefixCSum[i] = CSum;
        prefixGSum[i] = GSum;
        prefixTSum[i] = TSum;
        
    }
    
    for (let i = 0; i < P.length; i++) {
        if (prefixASum[Q[i]+1] - prefixASum[P[i]] > 0) {
            ans[i] = 1;
        } else if (prefixCSum[Q[i]+1] - prefixCSum[P[i]] > 0) {
            ans[i] = 2;
        } else if (prefixGSum[Q[i]+1] - prefixGSum[P[i]] > 0) {
            ans[i] = 3;
        } else {
            ans[i] = 4;
        }
    }
    
    return ans;

}

Note

https://codility.com/media/train/3-PrefixSums.pdf

PassingCars 100% Solution in Javascript

Question

app.codility.com

My Solution

app.codility.com

function solution(A) {
    
    let suffixSum = [];
    let sum = 0;
    let ans = 0;
    
    for (let i = A.length-1; i >= 0; i--) {
        sum += A[i];    
        suffixSum[i] = sum;
    }
    
    for (let i = 0; i < A.length; i++) {
        if (A[i] == 0)
            ans += suffixSum[i];   
        if (ans > 1000000000)
            return -1;
    }
    
    return ans;

}