Codility Lesson 05

Lesson 5

5.1 - Passing Cars

A non-empty array A consisting of N integers is given. The consecutive elements of array A represent consecutive cars on a road.

Array A contains only 0s and/or 1s:

• 0 represents a car traveling east,
• 1 represents a car traveling west.

The goal is to count passing cars. We say that a pair of cars (P, Q), where 0 ≤ P < Q < N, is passing when P is traveling to the east and Q is traveling to the west.

For example, consider array A such that:

  A[0] = 0
  A[1] = 1
  A[2] = 0
  A[3] = 1
  A[4] = 1

We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).

Write a function:

class Solution 
{
  public int solution(int[] A); 
}

that, 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:

  A[0] = 0
  A[1] = 1
  A[2] = 0
  A[3] = 1
  A[4] = 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.

using System;
using System.Collections.Generic;

/* Lesson 4.4 - Missing Integer
 * Paulo Santos
 * 24.Nov.2022
 */
class Solution {
    public int solution(int[] A) {
        
		/*
		 * Check the inputs
		 */
        if (A == null)
            throw new ArgumentNullException("A is null");

        /*
         * Separate the cars going left
         * from the cars going right
         */
        var zeros = new Queue<int>();
        var ones  = new Queue<int>();
        for(var i = A.Length - 1; i >= 0; i--) {
            if (A[i] == 0) zeros.Enqueue(i);
            if (A[i] == 1) ones.Enqueue(i);
        }

        /*
         * Compute the possiblities
         */
        var ans = 0; // answer to be given
        var cnt = 0; // counter
        while (zeros.Count > 0) {
            var z = zeros.Peek();
            while ((ones.Count > 0) && 
                   (z < ones.Peek())) {
                cnt++;
                ones.Dequeue();
            }
            ans += cnt;

            if (ans > 1000000000)
                return -1;
                
            zeros.Dequeue();
        }
        return ans;
    }
}

---

5.2 - Count Div

Write a function:

class Solution 
{
  public int solution(int A, int B, int K); 
}

that, 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.

using System;

/* Lesson 5.2 - Count Div
 * Paulo Santos
 * 30.Nov.2022
 */
class Solution {
    public int solution(int A, int B, int K) {

        /*
         * Check the inputs
         */
        if ((A < 0 || A > 2000000000) ||
            (B < 0 || B > 2000000000) ||
            (K < 0 || K *gt; 2000000000))
            throw new ArgumentOutOfRangeException();
        
        var C = (B - A);
        var res = (int)Math.Floor((decimal)C / K);
        if (((A % K) == 0) || ((B % K) == 0))
            return (res + 1);

        if ((K > A) && (K < B)) {
            C = (B - K);
            return (int)Math.Floor((decimal)C / K) + 1;
        }
        
        return res;
    }
}

---

5.3 - Genomic Range Query

A DNA sequence can be represented as a string consisting of the letters A, C, G and T, which correspond to the types of successive nucleotides in the sequence. Each nucleotide has an impact factor, which is an integer. Nucleotides of types A, C, G and T have impact factors of 1, 2, 3 and 4, respectively. You are going to answer several queries of the form: What is the minimal impact factor of nucleotides contained in a particular part of the given DNA sequence?

The DNA sequence is given as a non-empty string S = S[0]S[1]...S[N-1] consisting of N characters. There are M queries, which are given in non-empty arrays P and Q, each consisting of M integers. The K^-th query (0 ≤ K < M) requires you to find the minimal impact factor of nucleotides contained in the DNA sequence between positions P[K] and Q[K] (inclusive).

For example, consider 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 answers to these M = 3 queries are as follows:

• The part of the DNA between positions 2 and 4 contains nucleotides G and C (twice), whose impact factors are 3 and 2 respectively, so the answer is 2.
• The part between positions 5 and 5 contains a single nucleotide T, whose impact factor is 4, so the answer is 4.
• The part between positions 0 and 6 (the whole string) contains all nucleotides, in particular nucleotide A whose impact factor is 1, so the answer is 1.

Write a function:

class Solution 
{ 
  public int[] solution(string S, int[] P, int[] Q); 
}

that, 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.

using System;

/**
 * Lesson 5.3 - Genomic Range Query
 * Paulo Santos
 * 06.Dec.2022
 */
class Solution {
    public int[] solution(string S, int[] P, int[] Q) {
    int len = S.Length;
    var answers = new int[P.Length];
   
    var occurrences = new int [len, 4];
   
    /*
     * For each pos, indicate which 
     * nucleotide it is, and perform
     * a running sum, after the 
     * second position.
     *
     * Eexample. if S = "CAGCCTA" 
     * occurrences will be:
     *
     * {
     *  {0,1,0,0}  // C
     *  {1,1,0,0}  // A
     *  {1,1,1,0}  // G
     *  {1,2,0,0}  // C
     *  {1,3,0,0}  // C
     *  {1,3,1,1}  // T
     *  {2,3,1,1}  // A
     * }
     *
     */
    for(var i = 0; i < len; i++) {
      switch (S[i]) {
        case 'A': { occurrences[i, 0] = 1; break; }
        case 'C': { occurrences[i, 1] = 1; break; }
        case 'G': { occurrences[i, 2] = 1; break; }
        default : { occurrences[i, 3] = 1; break; }
      }
      if (i > 0) {
        occurrences[i, 0] += occurrences[i - 1, 0];
        occurrences[i, 1] += occurrences[i - 1, 1];
        occurrences[i, 2] += occurrences[i - 1, 2];
        occurrences[i, 3] += occurrences[i - 1, 3];
      }
    }
    
    /*
     * Check each slice for min by simple subtraction
     */
    for(var i = 0; i < P.Length; i++) {
      var index1 = P[i];
      var index2 = Q[i];

      for(var j = 0; j < 4; j++) { 
        /*
         * When index1 is not at the beginning
         * of the string, need to get occurrences
         * from just before beginning of the slice
         * to see if that nucleotide occurred
         * within the slice.
         *
         * Example: is slice is (2, 4), need to check
         * for occurrences of A, C, G, T from index 1 to 4 
         */
        int lic = 0; 
        if (index1 - 1 >= 0) {
          lic = occurrences[index1 - 1, j];
        }
       
        if(occurrences[index2, j] - lic > 0) {
          /*
           * nucleotide value is 1 more than 
           * loop value (A=1, C=2, G=3, T=4)
           */
          answers[i] = j + 1;
          
          /*
           * no need to keep checking since 
           * always checking from smallest 
           * impact factor as soon as find occurrence, 
           * that has to be minimum, cause 
           * subsequent nucleotides have
           * larger impact factor
           */
          break;
        }
      }
    }
    return answers;
  }
}

---

5.4 - Min Avg Two Slice

A non-empty array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P < Q < N, is called a slice of array A (notice that the slice contains at least two elements). The average of a slice (P, Q) is the sum of A[P] + A[P + 1] + ... + A[Q] divided by the length of the slice. To be precise, the average equals (A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1).

For example, array A such that:

    A[0] = 4
    A[1] = 2
    A[2] = 2
    A[3] = 5
    A[4] = 1
    A[5] = 5
    A[6] = 8

contains the following example slices:

• slice (1, 2), whose average is (2 + 2) / 2 = 2;
• slice (3, 4), whose average is (5 + 1) / 2 = 3;
• slice (1, 4), whose average is (2 + 2 + 5 + 1) / 4 = 2.5.

The goal is to find the starting position of a slice whose average is minimal.

Write a function:

class Solution 
{
  public int solution(int[] A); 
}

that, given a non-empty array A consisting of N integers, returns the starting position of the slice with the minimal average. If there is more than one slice with a minimal average, you should return the smallest starting position of such a slice.

For example, given array A such that:

    A[0] = 4
    A[1] = 2
    A[2] = 2
    A[3] = 5
    A[4] = 1
    A[5] = 5
    A[6] = 8

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 [−10,000..10,000].

using System;

/**
 * 5.4 - Min Avg Two Slice
 * Paulo Santos
 * 07.Dec.2022
 *
 * Thanks to Mr.Duhart 
 *        (https://stackoverflow.com/users/4281529/mr-duhart)
 */
class Solution {
    public int solution(int[] A) {
    
    /*
     * Find prefix sum.
     */
    int N = A.Length;
    var ps = new int[N + 1];
    
    for (int i = 1; i <= N; i++) {
        ps[i] = A[i - 1] + ps[i - 1];
    }

    int lftIdx, minLftIdx;
    double avgHere, minAvg, avgOfTwo, avgWithPrev;
    
    /*
     * Initialize variables at the first possible slice (A[0:1]).
     */
    lftIdx = minLftIdx = 0;
    avgHere = minAvg = (A[0] + A[1]) / 2.0;
    
    /*
     * Find min average of every slice that ends at ith element,
     * starting at i = 2.
     */
    for (int i = 2; i < N; i ++) {

        /*
         * average of A[lftIdx : i]
         */
        avgWithPrev = ((double) ps[i + 1] - ps[lftIdx]) / 
                        (i - lftIdx + 1);

        /*
         * average of A[i - 1 : i]
         */
        avgOfTwo = (A[i - 1] + A[i]) / 2.0;
        
        /*
         * Find minimum and update lftIdx of slice
         * (previous lftIdx or i - 1).
         */
        if (avgOfTwo < avgWithPrev) {
            avgHere = avgOfTwo;
            lftIdx = i - 1;
        }
        else
            avgHere = avgWithPrev;
        
        /*
         * Keep track of minimum so far and its left index.
         */
        if (avgHere < minAvg) {
            minAvg = avgHere;
            minLftIdx = lftIdx;
        }
    }
        
    return minLftIdx;
    }
}