Codility questions

Main.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication5
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            int[] A = { 4, 4, 4, 4, 4, 4, 5 };// 

            Console.WriteLine(string.Join(",", solution(A)));
            Console.Read();
        }

        //https://codility.com/programmers/task/missing_integer
        public static int solution1(int[] A)
        {
            if (A == null)
                return 0;

            int count = A.Length;

            if (count == 1)
            {
                return A[0] == 1 ? 2 : 1;
            }

            int sum = 0;

            for (int i = 0; i < count; i++)
            {
                sum = sum ^ A[i] ^ (i + 1);
            }

            sum = sum ^ (count + 1);

            return sum;
        }

        //https://codility.com/programmers/task/max_counters
        public static int[] solution(int N, int[] A)
        {
            int[] result = new int[N];

            if (A == null)
                return result;

            int count = A.Length;
            int maxBoundary = N + 1;
            int lastMax = -1;
            int currentMax = 0;

            if (count == 1)
            {
                if (A[0] < 0 || A[0] >= maxBoundary)
                    return result;

                result[A[0]]++;

                return result;
            }

            for (int i = 0; i < count; i++)
            {
                if (A[i] < 0 || A[i] > maxBoundary)
                    continue;

                if (A[i] < maxBoundary)
                {
                    if (lastMax != -1)
                        result[A[i] - 1] = result[A[i] - 1] < lastMax ? lastMax + 1 : result[A[i] - 1] + 1;
                    else
                    {
                        result[A[i] - 1]++;
                    }

                    if (result[A[i] - 1] > currentMax)
                        currentMax = result[A[i] - 1];
                }

                if (A[i] == maxBoundary)
                    lastMax = currentMax;
            }


            if (lastMax != -1)
            {
                for (int i = 0; i < N; i++)
                {
                    if (result[i] < lastMax)
                        result[i] = lastMax;
                }
            }

            return result;
        }

        //https://codility.com/c/run/trainingSERZTM-BD7
        public static int[] solution(string S, int[] P, int[] Q)
        {
            if (string.IsNullOrEmpty(S))
                return new int[] {};

            if (P == null || Q == null)
                return new int[] {};

            int count = S.Length;
            Dictionary<char, int> table = new Dictionary<char, int>
            {
                {'A', 0},
                {'C', 1},
                {'G', 2},
                {'T', 3},
            };

            if (count == 1)
                return Enumerable.Repeat(table[S[0]] + 1, P.Count()).ToArray();

            int[,] lastOccurences = new int[count, table.Count];
            int[] result = new int[P.Length];

            lastOccurences[0, table['A']] = -1;
            lastOccurences[0, table['C']] = -1;
            lastOccurences[0, table['G']] = -1;
            lastOccurences[0, table['T']] = -1;
            lastOccurences[0, table[S[0]]] = 0;

            for (int i = 1; i < count; i++)
            {

                lastOccurences[i, table['A']] = lastOccurences[i - 1, table['A']];
                lastOccurences[i, table['C']] = lastOccurences[i - 1, table['C']];
                lastOccurences[i, table['G']] = lastOccurences[i - 1, table['G']];
                lastOccurences[i, table['T']] = lastOccurences[i - 1, table['T']];
                lastOccurences[i, table[S[i]]] = i;
            }

            for (int i = 0; i < P.Length; i++)
            {
                if (S[P[i]] == 'A' || S[Q[i]] == 'A')
                {
                    result[i] = 1;
                }
                else
                {
                    for (int j = 0; j < table.Count; j++)
                    {
                        if (lastOccurences[Q[i], j] >= P[i])
                        {
                            result[i] = j + 1;
                            break;
                        }
                    }
                }
            }

            return result;
        }

        //https://codility.com/c/run/trainingWZCMTF-E69
        public static int solution2(int[] A)
        {
            if (A == null || A.Length == 1)
                return 0;

            int count = A.Length;
            Tuple<long, long>[] circles = A.Select((k, v) => Tuple.Create((long) v - k, (long) v + k)).OrderBy(x => x.Item1).ToArray();
            int circlesIntersections = 0;

            for (int i = 0; i < count - 1; i++)
            {
                int start = i + 1;
                int end = count;

                if (start > end)
                    break;

                if (circles[start].Item1 > circles[i].Item2)
                    continue;

                while (start + 1 < end)
                {
                    int mid = (end + start) / 2;

                    if (circles[mid].Item1 > circles[i].Item2)
                    {
                        end = mid;
                    }
                    else
                    {
                        start = mid;
                    }
                }

                circlesIntersections += end - i - 1;
            }

            return circlesIntersections;
        }

        //https://codility.com/c/run/trainingHMJGC2-YZC
        public static int solution3(int[] A)
        {
            //TODO: currently incorrect
            
            if (A == null || A.Length < 3)
                return 0;

            int count = A.Length;

            Dictionary<int, int> factorizationTable = new Dictionary<int, int>();
            List<int> peaks = new List<int>();

            for (int i = 1; i < count - 1; i++)
            {
                if (A[i - 1] < A[i] && A[i] > A[i + 1])
                    peaks.Add(i);
            }

            int maxDistance = -1;

            if (peaks.Any())
                maxDistance = peaks[0];

            if (peaks.Count > 1)
                maxDistance = Math.Max(maxDistance, count - 1 - peaks.Last());

            if (peaks.Count > 2)
            {
                for (int i = 1; i < peaks.Count; i++)
                {
                    maxDistance = Math.Max(maxDistance, peaks[i] - peaks[i - 1]);
                }
            }

            int bestBlocks = 1;
            int prevCount = count;
            int primeDivisor = 2;

            while (count > 1)
            {
                while (count % primeDivisor == 0)
                {
                    count /= primeDivisor;

                    if (factorizationTable.ContainsKey(primeDivisor))
                        factorizationTable[primeDivisor]++;
                    else
                        factorizationTable.Add(primeDivisor, 1);
                }

                primeDivisor++;
            }

            for (int i = 0; i < Math.Min(32, Math.Pow(2, factorizationTable.Count)); i++)
            {
                string s = Convert.ToString(i, 2);

                var factors = s.Where(c => c == '1').Select((v, k) => factorizationTable.ElementAt(factorizationTable.Count-k-1));

                var divisor = 1;

                foreach (var keyValuePair in factors)
                {
                    for (int j = 0; j < keyValuePair.Value; j++)
                    {
                        divisor *= keyValuePair.Key;

                        if (2 * prevCount / divisor < maxDistance && bestBlocks < divisor)
                            bestBlocks = divisor;
                    }
                } 
            }


            return bestBlocks;
        }

        //https://codility.com/c/run/trainingCWCMSQ-86H
        public static int solution(int[] A)
        {
            if (A == null || A.Length == 1)
                return 0;

            if (A.Length == 2)
            {
                return A[0] > A[1] ? 1 : 0;
            }

            int inversions;
            var sorted = sort(A, out inversions);

            return inversions;
        }

        private static int[] sort(int[] A, out int inversions)
        {
            inversions = 0;

            if (A.Length == 1)
                return A;

            int[] left = A.Take(A.Length / 2).ToArray();
            int[] right = A.Skip(A.Length / 2).ToArray();

            if (left.Length == 0)
                return right;


            if (right.Length == 0)
                return left;

            int inversionsLeft;
            int inversionsRight;

            left = sort(left, out inversionsLeft);
            right = sort(right, out inversionsRight);

            var sorted = merge(left, right, out inversions);

            inversions += inversionsLeft + inversionsRight;

            return sorted;
        }

        private static int[] merge(int[] A, int[] B, out int inversions)
        {

            inversions = 0;

            if (A == null || A.Length == 0)
                return B;

            if (B == null || B.Length == 0)
                return A;

            int[] C = new int[A.Length + B.Length];
            int turn = A[0] < B[0] ? 0 : 1;
            int indexA = 0;
            int indexB = 0;

            while (indexA < A.Length && indexB < B.Length)
            {
                if (turn == 0)
                {
                    if (A[indexA] <= B[indexB])
                    {
                        C[indexA + indexB] = A[indexA];
                        indexA++;
                    }
                    else
                    {
                        C[indexA + indexB] = B[indexB];
                        indexB++;
                        inversions += A.Length - indexA;
                        turn = 1;
                    }
                }
                else
                {
                    if (A[indexA] <= B[indexB])
                    {
                        C[indexA + indexB] = A[indexA];
                        turn = 0;
                        indexA++;
                    }
                    else
                    {
                        C[indexA + indexB] = B[indexB];
                        indexB++;
                        inversions += A.Length - indexA;
                    }
                }
            }

            if (indexA == A.Length)
            {
                for (int i = indexB; i < B.Length; i++)
                {
                    C[indexA + i] = B[i];
                }
            }
            else if (indexB == B.Length)
            {
                for (int i = indexA; i < A.Length; i++)
                {
                    C[indexB + i] = A[i];
                }
            }

            return C;
        }
    }
}