Codility Lesson 04

Lesson 4

4.1 - Frog River One

A small frog wants to get to the other side of a river. The frog is initially located on one bank of the river (position 0) and wants to get to the opposite bank (position X+1). Leaves fall from a tree onto the surface of the river.

You are given an array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in seconds.

The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X (that is, we want to find the earliest moment when all the positions from 1 to X are covered by leaves). You may assume that the speed of the current in the river is negligibly small, i.e. the leaves do not change their positions once they fall in the river.

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

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

In second 6, a leaf falls into position 5. This is the earliest time when leaves appear in every position across the river.

Write a function:

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

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

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

using System;
using System.Linq;
using System.Collections.Generic;

/* Lesson 4.1 - Frog River One
 * Paulo Santos
 * 24.Nov.2022
 */
class Solution {
    public int solution(int X, int[] A) {

        /*
         * Check the input
         */
        if (A == null)
            throw new ArgumentNullException();
            
        var riverLen = (X);
        var river = new Dictionary<int, int>();
        var ans = -1;
        var cnt = 0;
        for(var i = 0; i < A.Length; i++) {
            var rp = A[i] - 1;
            if (!river.ContainsKey(rp)) {
                river[rp] = i;
                cnt +=1;
            }
            else {
                river[rp] = Math.Min(i + 1, river[rp]);
            }

            if (cnt > riverLen)
                break;
        }

        for(var i = 0; i < riverLen; i ++)
            if (!river.ContainsKey(i))
                return -1;
        
        
        ans = river.Select(r => r.Value).Max();
        return ans;
    }
}

---

4.2 - Permutation Check

A non-empty array A consisting of N integers is given.

A permutation is a sequence containing each element from 1 to N once, and only once.

For example, array A such that:

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

is a permutation, but array A such that:

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

is not a permutation, because value 2 is missing.

The goal is to check whether array A is a permutation.

Write a function:

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

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

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

the function should return 1.

Given array A such that:

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

using System;

/* Lesson 4.2 - Perm Check
 * Paulo Santos
 * 24.Nov.2022
 */
class Solution {
    public int solution(int[] A) {

        /*
         * Check the input
         */
        if (A == null)
            throw new ArgumentNullException();
        
        Array.Sort(A);
        for (var i = 0; i < A.Length; i++)
            if (i != A[i] - 1)
                return 0;
        
        return 1;
    }
}

---

4.3 - Max Counters

You are given N counters, initially set to 0, and you have two possible operations on them:

• increase(X) − counter X is increased by 1,
• max counter − all counters are set to the maximum value of any counter.

A non-empty array A of M integers is given. This array represents consecutive operations:

if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),

if A[K] = N + 1 then operation K is max counter.

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

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

the values of the counters after each consecutive operation will be:

 (0, 0, 1, 0, 0)
 (0, 0, 1, 1, 0)
 (0, 0, 1, 2, 0)
 (2, 2, 2, 2, 2)
 (3, 2, 2, 2, 2)
 (3, 2, 2, 3, 2)
 (3, 2, 2, 4, 2)

The goal is to calculate the value of every counter after all operations.

Write a function:

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

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

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

using System;

/* Lesson 4.3 - Max Counter
 * Paulo Santos
 * 24.Nov.2022
 */
class Solution {
    public int[] solution(int N, int[] A) {

		/*
		 * Check the inputs
		 */
        if (A == null)
            throw new ArgumentNullException("A is null");
		if (N < 0)
			throw new ArgumentOutOfRangeException("N cannot be negative");
        
        var cnt = new int[N]; // counters
        var mct = new int[N]; // indicate the need to max the counter
        var max = 0;          // current max counter
        var mcc = 0;          // number of times the counter was maxed
        var mud = 0;          // max counter for update
        for(var i = 0; i < A.Length; i++) {
            /*
             * Check the command to see if it's to add the counter
             */
            var ord = A[i] - 1;
            if (0 <= ord && ord <= (N - 1)) {
                /*
                 * Check the need to max the counter
                 */
                if (mct[ord] != mcc) {
                    mct[ord] = mcc;
                    cnt[ord] = mud;
                }                    
                max = Math.Max(max, ++cnt[ord]);
            }
            else
            {
                /*
                 * Add the count to max the counters
                 */
                mcc++;
                mud = max;
            }
        }

        /*
         * Adjust the counters that were not maxed
         */
        for (var i = 0 ; i < cnt.Length; i++)
            if (mct[i] != mcc)
                cnt[i] = mud;

        return cnt;
    }
}

---

4.4 - Missing Integer

This is a demo task.

Write a function:

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

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

using System;

/* 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");

        var mis = 0;
        Array.Sort(A);
        for (var i = 0; i < A.Length; i++) {
            if (A[i] <= mis) 
                continue;

            if (++mis == A[i])
                continue;
            else if (mis < A[i])
                return mis;
        }
        return (mis == 0 ? 1 : mis + 1);
    }
}