Codility Lesson 15

15.1 - Absolute Distinct

A non-empty array A consisting of N numbers is given. The array is sorted in non-decreasing order. The absolute distinct count of this array is the number of distinct absolute values among the elements of the array.

For example, consider array A such that:

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

The absolute distinct count of this array is 5, because there are 5 distinct absolute values among the elements of this array, namely 0, 1, 3, 5 and 6.

Write a function:

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

that, given a non-empty array A consisting of N numbers, returns absolute distinct count of array A.

For example, given array A such that:

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

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 within the range [−2,147,483,648..2,147,483,647];
• array A is sorted in non-decreasing order.

using System;
using System.Collections.Generic;

/**
 * 15.1 - AbsDistinct
 * Paulo Santos
 * 15.Oct.2025
 */
class Solution {
    public int solution(int[] A) {
        var dic = new Dictionary<int, int>();
        foreach(var n in A) {
            var key = (n == int.MinValue ? n : Math.Abs(n));
            if(dic.ContainsKey(n))
                dic[key] += 1;
            else
                dic[key] = 1;
        }
        return dic.Count;
    }
}

---

15.2 - Count Distinct Slices

An integer M and a non-empty array A consisting of N non-negative integers are given. All integers in array A are less than or equal to M.

A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The slice consists of the elements A[P], A[P + 1], ..., A[Q]. A distinct slice is a slice consisting of only unique numbers. That is, no individual number occurs more than once in the slice.

For example, consider integer M = 6 and array A such that:

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

There are exactly nine distinct slices: (0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2), (3, 3), (3, 4) and (4, 4).

The goal is to calculate the number of distinct slices.

Write a function:

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

that, given an integer M and a non-empty array A consisting of N integers, returns the number of distinct slices.

If the number of distinct slices is greater than 1,000,000,000, the function should return 1,000,000,000.

For example, given integer M = 6 and array A such that:

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

the function should return 9, 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 [0..100,000];
• each element of array A is an integer within the range [0..M].

using System;

/**
 * 15.2 - Count Distinct Slices
 * Paulo Santos
 * 15.Oct.2025
 */
class Solution {
    public int solution(int M, int[] A) {
        int n = A.Length;
        int count = 0;
        int start = 0;
        
        var seen = new bool[M + 1];
        
        for (int end = 0; end < n; end++) {
            while (seen[A[end]]) {
                seen[A[start]] = false;
                start++;
            }
            
            seen[A[end]] = true;
            
            count += (end - start + 1);
            
            if (count > 1000000000) {
                return 1000000000;
            }
        }
        
        return count;
    }
}

---

15.3 - Count Triangles/h3>

An array A consisting of N integers is given. A triplet (P, Q, R) is triangular if it is possible to build a triangle with sides of lengths A[P], A[Q] and A[R]. In other words, triplet (P, Q, R) is triangular if 0 ≤ P < Q < R < N and:

• A[P] + A[Q] > A[R],
• A[Q] + A[R] > A[P],
• A[R] + A[P] > A[Q].

For example, consider array A such that:

A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 12

There are four triangular triplets that can be constructed from elements of this array, namely (0, 2, 4), (0, 2, 5), (0, 4, 5), and (2, 4, 5).

Write a function:

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

that, given an array A consisting of N integers, returns the number of triangular triplets in this array.

For example, given array A such that:

A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 12

the function should return 4, as explained above.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [0..1,000];
• each element of array A is an integer within the range [1..1,000,000,000].

using System;

/**
 * 15.3 - Counting Triangles
 * Paulo Santos
 * 17.Oct.2025
 */
public class Solution
{
    public int solution(int[] A)
    {
        if (A == null || A.Length < 3) return 0;

        Array.Sort(A);
        long count = 0;

        for (int k = 2; k < A.Length; k++)
        {
            int i = 0, j = k - 1;
            while (i < j)
            {
                long sum = (long)A[i] + A[j];
                if (sum > A[k])
                {
                    count += (j - i);
                    j--;
                }
                else
                {
                    i++;
                }
            }
        }

        return (int)count;
    }
}

---

15.4 - Min Absolute Sum of Two/h3>

Let A be a non-empty array consisting of N integers.

The abs sum of two for a pair of indices (P, Q) is the absolute value |A[P] + A[Q]|, for 0 ≤ P ≤ Q < N.

For example, the following array A:

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

has pairs of indices (0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2).
The abs sum of two for the pair (0, 0) is A[0] + A[0] = |1 + 1| = 2.
The abs sum of two for the pair (0, 1) is A[0] + A[1] = |1 + 4| = 5.
The abs sum of two for the pair (0, 2) is A[0] + A[2] = |1 + (−3)| = 2.
The abs sum of two for the pair (1, 1) is A[1] + A[1] = |4 + 4| = 8.
The abs sum of two for the pair (1, 2) is A[1] + A[2] = |4 + (−3)| = 1.
The abs sum of two for the pair (2, 2) is A[2] + A[2] = |(−3) + (−3)| = 6.

Write a function:

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

that, given a non-empty array A consisting of N integers, returns the minimal abs sum of two for any pair of indices in this array.

For example, given the following array A:

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

the function should return 1, as explained above.

Given array A:

A[0] = -8 A[1] = 4 A[2] = 5 A[3] =-10 A[4] = 3

the function should return |(−8) + 5| = 3.

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,000..1,000,000,000].

using System;

/**
 * 15.4 - Min Absolute Sum of Two
 * Paulo Santos
 * 17.Oct.2025
 */
public class Solution
{
    public int solution(int[] A)
    {
        Array.Sort(A);
        int n = A.Length;
        int i = 0, j = n - 1;
        long best = long.MaxValue;

        while (i <= j)
        {
            long s = (long)A[i] + A[j];
            long abs = s >= 0 ? s : -s;
            if (abs < best) best = abs;

            if (s > 0) j--;
            else if (s < 0) i++;
            else return 0;
        }

        return (int)best;
    }
}