Codility Developer Training

Codility Training - frog-river-one.js

/**
given a non-empty array A consisting of N integers and integer X, returns the earliest time when the frog can jump to the other side of the river.

If the frog is never able to jump to the other side of the river, the function should return −1.

For example, given X = 5 and array A such that:

  [1, 3, 1, 4, 2, 3, 5, 4]
  
the function should return 6, as explained above.

Write an efficient algorithm for the following assumptions:

N and X are integers within the range [1..100,000];
each element of array A is an integer within the range [1..X].
*/
function solution(X, A) {
    if (A.length === 1) {
        return A[0] === 1 && X === 1 ? 0 : -1;
    }

    const steps = [1];
    let maxD = 0;
    for (var sec=0; sec< A.length; sec++) {
        steps[A[sec]] = 1;
        for (var d=maxD; d < steps.length; d++) {
            if (!steps[d]) break;
            maxD = d;
        }
        if (maxD >= X) {
            return sec;
        }
    }
    return -1;
}

count-div.js

/**
given three integers A, B and K, returns the number of integers within the range [A..B] that are divisible by K, i.e.:

{ i : A ≤ i ≤ B, i mod K = 0 }

For example, for A = 6, B = 11 and K = 2, your function should return 3, because there are three numbers divisible by 2 within the range [6..11], namely 6, 8 and 10.

Write an efficient algorithm for the following assumptions:

A and B are integers within the range [0..2,000,000,000];
K is an integer within the range [1..2,000,000,000];
A ≤ B.
*/

function solution(A, B, K) {
    const sta = Math.floor( A / K);
    const end = Math.floor( B / K);
    const inclusive = A % K === 0;

    return end - sta + inclusive;
}

DNA-genome-range-query.js

/**
given a non-empty string S consisting of N characters and two non-empty arrays P and Q consisting of M integers, returns an array consisting of M integers specifying the consecutive answers to all queries.

Result array should be returned as an array of integers.

For example, given the string S = CAGCCTA and arrays P, Q such that:

    P[0] = 2    Q[0] = 4
    P[1] = 5    Q[1] = 5
    P[2] = 0    Q[2] = 6
the function should return the values [2, 4, 1], as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];
M is an integer within the range [1..50,000];
each element of arrays P and Q is an integer within the range [0..N - 1];
P[K] ≤ Q[K], where 0 ≤ K < M;
string S consists only of upper-case English letters A, C, G, T.
*/

function solution(S, P, Q) {
    const impacts = [];
    for (var i=0; i < P.length; i++) {
        const sta = P[i];
        const end = Q[i]+1;
        const str = S.slice(sta, end);

        if (str.indexOf('A') !== -1)
            impacts.push(1);
        else if (str.indexOf('C') !== -1) 
            impacts.push(2);
        else if (str.indexOf('G') !== -1) 
            impacts.push(3);
        else
            impacts.push(4)
    }
    return impacts;
}

max-counters.js

/**
given an integer N and a non-empty array A consisting of M integers, returns a sequence of integers representing the values of the counters.

Result array should be returned as an array of integers.

For example, given: [3,4,4,6,1,4,4]

the function should return [3, 2, 2, 4, 2], as explained above.

Write an efficient algorithm for the following assumptions:

N and M are integers within the range [1..100,000];
each element of array A is an integer within the range [1..N + 1].
*/

function solution(N, A) {
    let counter = Array(N).fill(0);
    let max = 0, resetNum = 0;
    for(var i = 0; i < A.length; i++) {
        if (A[i] > N) {
            resetNum = max;   
        } else {  // if value within a range
            const pos = A[i] - 1; // e.g. 3 is index 2. [0,0,1]
            if (counter[pos] < resetNum) { // if value is less than resetNum
                counter[pos] = resetNum+1; //   discard old one, and set as resetNum +1
            } else {                       // if value is greater/equal to resetNum
                counter[pos]++;            //   simply increase 1
            }
            max = Math.max(max, counter[pos]); // update max
        }
        // console.log(counter, resetNum)
    }  

    for(let i = 0; i < N; i++){
        if (counter[i] < resetNum)
            counter[i] = resetNum;
    }    
    return counter;
}

missing-integer.js

/**
given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.

For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.

Given A = [1, 2, 3], the function should return 4.

Given A = [−1, −3], the function should return 1.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];
each element of array A is an integer within the range [−1,000,000..1,000,000].
*/

function solution(A) {
    const counter = []
    A.forEach(el => {
        if (el>0) 
            counter[el] = 1
    });

    for (var i=1; i<counter.length; i++) {
        if (!counter[i]) break;
    }
    return i;
}

passing-cars.js

/**
given a non-empty array A of N integers, returns the number of pairs of passing cars.

The function should return −1 if the number of pairs of passing cars exceeds 1,000,000,000.

For example, given: [0, 1, 0, 1, 1 ]

the function should return 5, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];
each element of array A is an integer that can have one of the following values: 0, 1.

val      | 0  |  1 | 0  |  1 |  1  |
east     | -> |    | -> |    |     |
west     |    | <- |    | <- | <-  |
eastCars | 1  | 2  |    |    |     |
pairs    |    | 1  |    | 2  | 2   |====> 5   
*/

function solution(A) {
    let eastCars = 0;
    let pairs = 0;

    for (var i=0; i<A.length; i++) {
        const eastCar = A[i] === 0;
        if (eastCar) 
            eastCars++;
        else // westcar, meets east-bound passing cars
            pairs += eastCars;
        
        // console.log({eastCar, eastCars, pairs})
        if (pairs > 1000000000) return -1;
    }
    return pairs;
}

permutation-check.js

/**
given an array A, returns 1 if array A is a permutation and 0 if it is not.

For example, given array A such that: [4,1,3,2]
the function should return 1.

Given array A such that: [4,1,3]
the function should return 0.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];
each element of array A is an integer within the range [1..1,000,000,000].
*/

function solution(A) {
    let max=0;
    const counter = []; // antisum
    const sum = A.reduce( (acc, cur, index) => {
        if (cur>max) max = cur;
        if (counter[cur] > 0)  // antisum
            return 0
        counter[cur] = 1; // antisum
        return acc+cur
    }, 0);

    const permutatedSum = max * (max+1) / 2;
    return sum === permutatedSum ? 1 : 0
}


function solution(A) {
    const max = Math.max.apply(this, A);
    const set = new Set(A);

    if (A.length != set.size) // deduped size !== org size
        return 0;

    const sum = A.reduce( (acc, cur) => acc+cur, 0);
    return sum === (max*(max+1)/2) ? 1 : 0;
}

tape-equilibrium.js

/**
given a non-empty array A of N integers, returns the minimal difference that can be achieved.

For example, given: [3, 1, 2, 4, 3]

the function should return 1, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [2..100,000];
each element of array A is an integer within the range [−1,000..1,000].
*/

function solution(A) {
  const total = A.reduce( (acc, cur) => acc + cur, 0);
  if (A.length === 1) return total;
  if (A.length === 2) return Math.abs(A[0] - A[1])
  
  var leftSum=0, rightSum=0, diff=0, min = 100000;
  for (var i=1; i<A.length; i++) {
      leftSum += A[i - 1];
      rightSum = total - leftSum;
      diff = Math.abs(leftSum - rightSum);
      min =diff < min ? diff : min
  }

  return min;
}