Codility Lesson 08

8.1 - Dominator

An array A consisting of N integers is given. The dominator of array A is the value that occurs in more than half of the elements of A.

For example, consider array A such that

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

The dominator of A is 3 because it occurs in 5 out of 8 elements of A (namely in those with indices 0, 2, 4, 6 and 7) and 5 is more than a half of 8.

Write a function

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

that, given an array A consisting of N integers, returns index of any element of array A in which the dominator of A occurs. The function should return −1 if array A does not have a dominator.

For example, given array A such that

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

the function may return 0, 2, 4, 6 or 7, as explained above.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [0..100,000];
• each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

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

/**
 * 8.1 - Dominator
 * Paulo Santos
 * 09.Dec.2022
 */
class Solution {

    struct Info {
        public Info(int i) {
            this.Index = i + 1;
            this.Count = 1;
        }

        public int Index {get; set;}
        public int Count {get; set;}
    }

    public int solution(int[] A) {

        var dic = new Dictionary<int, Info>();

        for(var i = 0; i < A.Length; i++) {
            if (dic.ContainsKey(A[i])) {
                var p = dic[A[i]];
                p.Count++;
                dic[A[i]] = p;
            }
            else
                dic[A[i]] = new Info(i);
        }

        var res = dic.Where(x=>x.Value.Count > (A.Length / 2))
                     .Select(x=>x.Value.Index)
                     .OrderBy(x=>x)
                     .FirstOrDefault();

        return (res == 0 ? -1 : res - 1);
    }
}

---

8.2 - Equi Leader

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

The leader of this array is the value that occurs in more than half of the elements of A.

An equi leader is an index S such that 0 ≤ S < N − 1 and two sequences A[0], A[1], ..., A[S] and A[S + 1], A[S + 2], ..., A[N − 1] have leaders of the same value.

For example, given array A such that:

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

we can find two equi leaders:

• 0, because sequences: (4) and (3, 4, 4, 4, 2) have the same leader, whose value is 4.
• 2, because sequences: (4, 3, 4) and (4, 4, 2) have the same leader, whose value is 4.

The goal is to count the number of equi leaders.

Write a function:

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

that, given a non-empty array A consisting of N integers, returns the number of equi leaders.

For example, given:

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

the function should return 2, 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 [−1,000,000,000..1,000,000,000].

using System;
using System.Collections.Generic;

/**
 * 8.2 - Equi Leader
 * Paulo Santos
 * 09.Dec.2022
 */
class Solution {
    public int solution(int[] A) {

        var len = A.Length;
        var dic = new Dictionary<int, int>();
        var cnt = 0;
        var lead = 0;
        var equiLeader = 0;

        foreach(var i in A) {
            if (dic.ContainsKey(i)) {
                dic[i]++;
                if (dic[i] > cnt) {
                    cnt = dic[i];
                    lead = i;
                }
            }
            else
                dic[i] = 1;
        }

        if (cnt <= (len / 2))
            return 0;
        
        var lft = 0;
        var rgt = cnt;
        for (var i = 0; i < len; i++) {
            if (A[i] == lead) {
                lft += 1;
                rgt -= 1;
            }
            if ((lft > ((i + 1) / 2)) && 
                (rgt > ((len - i - 1) / 2))) {
                equiLeader += 1;
            }
        }

        return equiLeader;
    }
}