Codility Practice

Let's see how it goes

July 19, 2021

I recently started to brush up on my algorithms because.. I’m unemployed.

I decided to start by doing some codility practice. Here are some solutions that I wrote/came across. I’ll write another post regarding my revision I did next time.

PermCheck
PermMissingElem
FrogRiverOne
MissingInteger
MaxCounters
FrogRiverOne
TapeEquilibrium
PermMissingElem
FrogJmp
OddOccurrencesInArray
CyclicRotation
BinaryGap
CountDiv
PassingCars
MinAvgTwoSlice
Distinct
MaxProductOfThree

PermCheck

Check whether array A is a permutation.

https://app.codility.com/programmers/lessons/4-counting_elements/perm_check/ https://app.codility.com/demo/results/training37AY6U-6ER/

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)

    // Think of these are fake 
    let array = [];
    
    for(let i = 0; i < A.length; ++i) {
        // Early rejection check for duplication or if it's bigger than our length
        if (array[A[i] - 1] || A[i] > A.length) {
            return 0;
        }
        array[A[i] - 1] = true;
    }

    // Check again if we have any holes in our array, once found, reject again.
    for(let i = 0; i < A.length; ++i) {
        if(!array[i]) {
            return 0;
        }
    }
    
    
    return 1;
}

PermMissingElem

Find the missing element in a given permutation.

https://app.codility.com/demo/results/training2SQDY8-WVW/

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)

    let missingNumber = A.length + 1;
    for(let i = 0; i < A.length; ++i) {
       missingNumber ^= (i + 1) ^ A[i];
    }
    
    return missingNumber;
}

FrogRiverOne

Find the earliest time when a frog can jump to the other side of a river.

https://app.codility.com/demo/results/trainingMC9U6Q-XZZ/

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(X, A) {
    // write your code in JavaScript (Node.js 8.9.4)

    let counts = new Set();
    for(let i = 0; i < A.length; ++i){
        counts.add(A[i]); // Note, there is no need to do if-else check, since it says a leaf wont fall outside of where we wanna go.
        if (counts.size === X) {
            return i;
        }
    }
    return -1;
}

MissingInteger

Find the smallest positive integer that does not occur in a given sequence.

https://app.codility.com/demo/results/trainingN4GPVZ-H9H/

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)

    let set = new Set();

    for(let i = 0; i < A.length; ++i) {
        set.add(A[i]);
    }

    for(let i = 1; i < 10000000; ++i) {
        if (!set.has(i)) {
            return i;
        }
    }

    return 1;
}

MaxCounters

Calculate the values of counters after applying all alternating operations: increase counter by 1; set value of all counters to current maximum.

https://app.codility.com/demo/results/trainingFD6JMJ-AY7/

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(N, A) {
    // write your code in JavaScript (Node.js 8.9.4)
    let arr = new Array(N).fill(0);
    let startingLine = 0;
    let legitLeadingValue = 0;
    // Loop through all instructions.
    for (let i = 0; i < A.length; ++i) {
        // if 6 > 5
        if(A[i] > N) {
            startingLine = Math.max(legitLeadingValue, startingLine);
            // console.log("fur:", legitLeadingValue, startingLine)
        } else {
            // arr.fill(trackMax);
            // We update for those that is at/after `furthest`
            // console.log(A[i], arr[A[i] - 1],  startingLine)
            if(arr[A[i] - 1] >= startingLine) {
                ++arr[A[i] - 1];
            } else { // If this has fallen behind, then we need to catch up.
                arr[A[i] - 1] = startingLine + 1;
            }
            legitLeadingValue = Math.max(legitLeadingValue, arr[A[i] - 1]);
            // console.log(arr)
        }
    }
    // console.log(startingLine, arr)
    // Make sure to catch up those that has not has a chance to increment after that last `furthest`.
    for(let i = 0; i < arr.length; ++i) {
        if(arr[i] < startingLine) {
            arr[i] = startingLine;
        }
    }

    return arr;
}

FrogRiverOne

Find the earliest time when a frog can jump to the other side of a river.

https://app.codility.com/demo/results/trainingMC9U6Q-XZZ/

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(X, A) {
    // write your code in JavaScript (Node.js 8.9.4)

    let counts = new Set();
    for(let i = 0; i < A.length; ++i){
        counts.add(A[i]);
        if (counts.size === X) {
            return i;
        }
    }
    return -1;
}

TapeEquilibrium

Minimize the value |(A[0] + … + A[P-1]) - (A[P] + … + A[N-1])|.

https://app.codility.com/demo/results/trainingTSRT8E-M97/

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)


    // Get the total sum first.
    let total = A.reduce((prevValue, currValue) => {
        return prevValue + currValue;
    }, 0);

    let totalLeft = A[0];
    let totalRight = total - A[0];

    let minDiff = Math.abs(totalRight - totalLeft);

    // console.log(totalLeft, totalRight, minDiff)

    // Start from 1, cos P starts from index 1.
    for(let i = 1; i < A.length - 1; ++i) {
        totalLeft += A[i];
        totalRight -= A[i];
        let diff = Math.abs(totalLeft - totalRight);
        minDiff = Math.min(minDiff, diff);
    }

    return minDiff;
}

https://app.codility.com/demo/results/trainingMXT5A7-SJA/ This should be wrong cos it checks first, but somehow it passes the test, so idk.

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)


    // Get the total sum first.
    let total = A.reduce((prevValue, currValue) => {
        return prevValue + currValue;
    }, 0);

    let totalLeft = A[0];
    let totalRight = total - A[0];

    let minDiff = Math.abs(totalRight - totalLeft);

    // console.log(totalLeft, totalRight, minDiff)

    // Start from 1, cos P starts from index 1.
    for(let i = 1; i < A.length; ++i) {
        let diff = Math.abs(totalLeft - totalRight);
        minDiff = Math.min(minDiff, diff);
        totalLeft += A[i];
        totalRight -= A[i];
    }

    return minDiff;
}

PermMissingElem

Find the missing element in a given permutation.

https://app.codility.com/demo/results/training7YKBXD-UM7/

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)

    let number = 0;
    for(let i = 0; i < A.length; ++i) {
        number ^= (i + 1) ^ A[i];
    }

    return number ^ (A.length + 1);
}

FrogJmp

Count minimal number of jumps from position X to Y.

https://app.codility.com/demo/results/trainingBMF5WN-TEU/

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(X, Y, D) {
    // write your code in JavaScript (Node.js 8.9.4)

    let difference = Y - X;
    return Math.ceil(difference / D);
}

OddOccurrencesInArray

Find value that occurs in odd number of elements

https://app.codility.com/demo/results/trainingABP4VG-Y8T/

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)

    let result = 0;
    for(let i = 0; i < A.length; ++i) {
        result ^= A[i];
    }
    return result;
}

https://app.codility.com/demo/results/trainingYVGSM3-R6S/

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    let hash = new Map();

    for(let i = 0; i < A.length; ++i) {
        hash.set(A[i], !!!hash.get(A[i]));
    }

    let unpairedElement = 0;
    
    hash.forEach((value, key) => {
        if (value) {
            unpairedElement = key;
        }
    });

    return unpairedElement;
}

CyclicRotation

Rotate an array to the right by a given number of steps.

https://app.codility.com/demo/results/trainingCDVSV2-PTG/

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A, K) {
    // write your code in JavaScript (Node.js 8.9.4)
    K = K % A.length;
    return [...A.slice(A.length - K), ...A.slice(0, A.length - K)];
}

BinaryGap

Find longest sequence of zeros in binary representation of an integer.

https://app.codility.com/demo/results/trainingU5C7P8-FRF/

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(N) {
    // write your code in JavaScript (Node.js 8.9.4)
    // Convert decimal to binary string.
    let binary = N.toString(2);
    let max = 0;
    let current = 0;
    for(let i = 0; i < binary.length; ++i) {
        if (binary[i] == 0) {
            ++current;
        } else {
            if (current > max) {
                max = current;
            }
            current = 0;
        }
    }

    return max;
}

https://app.codility.com/demo/results/trainingR6N8CK-UGT/

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(N) {
    // write your code in JavaScript (Node.js 8.9.4)
    
    // Do not convert to string and parse char by char!
    // Parse it as a number in bits! So end up lgN time.
    let maxCount = 0;
    let currCount = 0;
    let oneEncountered = false;
    while(N) {
        if(N & 1) {
            if(oneEncountered) {
                maxCount = Math.max(maxCount, currCount);
                oneEncountered = false;
            }

                // Reset.
                oneEncountered = true;
                currCount = 0;
            
        } else {
            ++currCount;
        }
        N >>= 1;
    }
    return maxCount;
}

CountDiv

Compute number of integers divisible by k in range [a..b].

https://app.codility.com/demo/results/training4TWSMH-WBT/

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A, B, K) {
    // write your code in JavaScript (Node.js 8.9.4)

    // Idea is to ensure A and B are multiples of K, then should be no issue.
    A = Math.trunc((A + K - 1) / K) * K; // Find next higher num divisible by K if A is not already. Using truncation trick to discard decimals.
    B = Math.trunc(B / K) * K; // Find the next lower num divisible by K if B is not already. Using truncation trick to discard decimals. Apparently we don't even need this step, 
    // In cases where A=4,B=6,K=3000, A will end up to be 3000. B will be 0. So we need to check for this case too.
    // Same for A=6,B=9,K=5 which should return 0. If not, it will return 1... so the check is needed.
    // NVM this is not needed because we find our next lower divisible by K for B already. IF WE DIDN't, then we need this.
    // EG given the above example, A=10, B=5, and 5-10 = -5. And -5/5 = -1 + 1 = 0!
    if(A > B) return 0;
    // Given B-A are multiples of K, e.g. [16,18,20] for K=2, 20-16 = 4, 4/2 = 2. 2 + 1 since we need to count A/B as well and we know it is divisible.
    return Math.trunc((B - A) / K) + 1;

    // Note we cannot do (B + A) / K, BECAUSE the extra from A and B can add up to another K.
    // Eg. A = 15, B = 25. K = 10. Answer we know is 1 (20 is divisible). BUT 15+25 = 40, gives us 4 which is wrong!
    // Alternate solution is if we take 25/10 = 2 and 15/10=1, 2-1 = 1 and add 1 if A is also divisible but I don't understand this at all and don't see how this uses prefix sums.
}

PassingCars

Count the number of passing cars on the road. Question https://stackoverflow.com/a/55867426/321629 - how many times the cars passed each other.

https://app.codility.com/demo/results/trainingUGZFT9-6RR/

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)

    // Idea here is to track how many cars going from Left-to-Right (East/0).
    // Then when we see a Right-to-Left car (West/1), we know how many Left-to-Right car it will pass later.
    let leftToRightCars = 0;
    let pathCrossCount = 0;
    for(let i = 0; i < A.length; ++i) {
        if(A[i] === 0) {
            ++leftToRightCars;
        } else { // This is a Left-to-Right car and will pass leftToRightCars amount of cars.
            pathCrossCount += leftToRightCars;
            // The function should return -1 if the number of pairs of passing cars exceeds 1,000,000,000.
            if (pathCrossCount > 1000000000) {
                return -1;
            }
        }
    }
    return pathCrossCount;
}

MinAvgTwoSlice

Find the minimal average of any slice containing at least two elements.

https://app.codility.com/demo/results/trainingWD7YGJ-2N8/

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)

    // Calculate presum for easier averaging later. But since we need to use A values later, we need to create a new prefix sum array instead of reusing A.
    let presum = new Array(A.length);
    presum[0] = A[0];
    for(let i = 1; i < A.length; ++i) {
        presum[i] = presum[i - 1] + A[i];
    }


    // This is the working P, required since we need to know start index to calculate average, unlike in max sum slices problem, we just need to keep track of running sum there. But not here, we need to recalculate each time.
    let startSliceIndex = 0;

    // Value of the average value of slice so far. Set to max since we are counting down.
    let prevMinAverageSlice = Number.MAX_SAFE_INTEGER;

    // Lowest P detected so far, defaults to 0.
    let minSliceLowestIndexP = 0;

    // Using Kadane's algorithm (?) to figure out the min average value (i.e. instead of using it to find max sum slice, we find min sum + average).
    // Start from index 1 since no point to start from 0.
    for(let q = 1; q < A.length; ++q) {
        // Let's calculate average. After calculating the difference, we need to add back P, since we are taking difference (still need to include the value of the leftmost value which is P). Difference is the sum of (P+1)..+.. (Q), hence need to add value of (P) itself. Same for divisor, need to add 1.
        let averageWithQ = (presum[q] - presum[startSliceIndex] + A[startSliceIndex]) / (q - startSliceIndex + 1);
        // Check current average with previous average to see which average is smaller and we will update it to prep for next loop.
        if (averageWithQ < prevMinAverageSlice) {
            prevMinAverageSlice = averageWithQ;
            // startSliceIndex is confirmed our smallest start index for now, so we just store it everytime.
            minSliceLowestIndexP = startSliceIndex;
        }
        // If A[q] itself is smaller than the new global average `prevMinAverageSlice`, it means A[q] helped to pull down the global average, and should discard the previous slices so far, and A[q] will be start of new slice.
        if(A[q] < prevMinAverageSlice) {
            startSliceIndex = q;
            // Note that startSliceIndex is not the CONFIRMED smallest slice yet, so we cannot use startSliceIndex as our return value, and hence we have a minSliceLowestIndexP.
        }
    }

    return minSliceLowestIndexP;
}

Distinct

Compute number of distinct values in an array.

https://app.codility.com/demo/results/trainingKWMW3K-HYZ/

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)
    let set = new Set();
    for(let i = 0; i < A.length; ++i){
        set.add(A[i])
    }
    return set.size;
}

MaxProductOfThree

Maximize A[P] * A[Q] * A[R] for any triplet (P, Q, R).

https://app.codility.com/demo/results/trainingM66JJ8-KNE/

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(A) {
    // write your code in JavaScript (Node.js 8.9.4)

    // Since this is a sorting qn... just use sort instead of loop (which might be faster since guaranteed O(n) for that).
    A.sort((a, b) => a - b);
    let length = A.length;
    return Math.max(A[length-1] * A[length-2] * A[length-3], A[length-1] * A[0] * A[1]);
}