PROBLEM:

A non-empty zero-indexed 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. The sum of a slice (P, Q) is the total of A[P] + A[P+1] + ... + A[Q].

Write a function:

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

that, given an array A consisting of N integers, returns the maximum sum of any slice of A.

For example, given array A such that:

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

the function should return 5 because:

• (3, 4) is a slice of A that has sum 4,
• (2, 2) is a slice of A that has sum −6,
• (0, 1) is a slice of A that has sum 5,
• no other slice of A has sum greater than (0, 1).

Assume that:

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

Complexity:

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

Copyright 2009–2015 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

SOLUTION (100%, time complexity O9N))

(click here for the full test report)

class Solution { public int solution(int[] A) { // write your code in C# 6.0 with .NET 4.5 (Mono) long max_end=-1000000; long max_slice=-1000000; int l= A.Length; if (l ==1) return A[0]; for (int i=0; i<l; i++) { max_end=Math.Max(A[i], max_end+A[i]); max_slice=Math.Max(max_slice, max_end); } return (int) max_slice; } }

The method is actually quite well explained here:

https://codility.com/media/train/7-MaxSlice.pdf

CODILITY - LESSON 6 - EquiLeader

PROBLEM:

A non-empty zero-indexed 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.

SOLUTION (100% score, time complexity O(N))

(click here to see the full test results)

class Solution { public int solution(int[] A) { int n = A.Length; int size =0; int value=0; Stack<int> s = new Stack<int>(); for (int i=0; i<n; i++) { if(size ==0) { size +=1; s.Push(A[i]); } else { if (s.Peek() != A[i]) size -=1; else size +=1; } } int candidate = -1; if (size>0) candidate = s.Peek(); int count =0; int leader= -1; for (int i=0; i<n; i++) { if (A[i] == candidate) count +=1; if (count > n/2) leader = candidate; } int equiLeaders=0; int leaders=0; for (int i=0; i<n; i++) { if (A[i] == leader) leaders++; if (leaders >(i+1)/2 && count-leaders >(n-1-i)/2) equiLeaders++; } return equiLeaders; } }

We can reuse the code that calculates the leader in the previous test (Lesson 6 - Dominator) and take advantage of having the leader and the number of occurrences of this leader.

Then we just loop the array from the first to the last element to see for those positions with the element leader are equi leaders.

PR

CODILITY - LESSON 5 - StoneWall

THE PROBLEM:

You are going to build a stone wall. The wall should be straight and N meters long, and its thickness should be constant; however, it should have different heights in different places. The height of the wall is specified by a zero-indexed array H of N positive integers. H[I] is the height of the wall from I to I+1 meters to the right of its left end. In particular, H[0] is the height of the wall's left end and H[N−1] is the height of the wall's right end.

The wall should be built of cuboid stone blocks (that is, all sides of such blocks are rectangular). Your task is to compute the minimum number of blocks needed to build the wall.

Write a function:

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

that, given a zero-indexed array H of N positive integers specifying the height of the wall, returns the minimum number of blocks needed to build it.

For example, given array H containing N = 9 integers:

  H[0] = 8    H[1] = 8    H[2] = 5
  H[3] = 7    H[4] = 9    H[5] = 8
  H[6] = 7    H[7] = 4    H[8] = 8

the function should return 7. The figure shows one possible arrangement of seven blocks.

THEIR SOLUTION:

(click here to go to their blog for more explanation)

(click here to see the full test results for this solution in c#)

class Solution {

    public int solution(int[] H) {

        // write your code in C# 6.0 with .NET 4.5 (Mono)

      

        int L = H.Length;

        int stones =0;

        int [] wall = new int [L];

        int wallNum=0;

        

        for (int i=0; i<L; i++)

        {

            while (wallNum>0 && wall[wallNum-1] > H[i]) wallNum -=1;   

            if (wallNum >0 && wall[wallNum -1] == H[i]) continue;

            else 

                {

                    stones +=1;

                    wall[wallNum] = H[i];

                    wallNum +=1;     

                }

        }

        return stones;

    }

}

It took me forever to understand the problem, and then it took me forever to come up with a solution that didn't fully work. I ended up checking their blog to see if the problem was better explained and then I read their solution and just couldn't take it off my mind. So I re wrote it in C#. Then it was just too late to come up with something completely mine! (specially because I didn't like the problem)

PR

CODILITY - LESSON 5 - Fish

THE PROBLEM:

You are given two non-empty zero-indexed arrays A and B consisting of N integers. Arrays A and B represent N voracious fish in a river, ordered downstream along the flow of the river.

The fish are numbered from 0 to N − 1. If P and Q are two fish and P < Q, then fish P is initially upstream of fish Q. Initially, each fish has a unique position.

Fish number P is represented by A[P] and B[P]. Array A contains the sizes of the fish. All its elements are unique. Array B contains the directions of the fish. It contains only 0s and/or 1s, where:

• 0 represents a fish flowing upstream,
• 1 represents a fish flowing downstream.

If two fish move in opposite directions and there are no other (living) fish between them, they will eventually meet each other. Then only one fish can stay alive − the larger fish eats the smaller one. More precisely, we say that two fish P and Q meet each other when P < Q, B[P] = 1 and B[Q] = 0, and there are no living fish between them. After they meet:

• If A[P] > A[Q] then P eats Q, and P will still be flowing downstream,
• If A[Q] > A[P] then Q eats P, and Q will still be flowing upstream.

We assume that all the fish are flowing at the same speed. That is, fish moving in the same direction never meet. The goal is to calculate the number of fish that will stay alive.

For example, consider arrays A and B such that:

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

Initially all the fish are alive and all except fish number 1 are moving upstream. Fish number 1 meets fish number 2 and eats it, then it meets fish number 3 and eats it too. Finally, it meets fish number 4 and is eaten by it. The remaining two fish, number 0 and 4, never meet and therefore stay alive.

THE SOLUTION (100% score, time complexity O(N))

(click here to see the full test results)

class Solution {

    public int solution(int[] A, int[] B) {

  Stack<int> aliveFishes = new Stack<int>();  

  for(int i = 0; i < A.Length; i++)

  {

       if(aliveFishes.Count==0)

       {

               aliveFishes.Push(i);

       }

       else

       {

               while(aliveFishes.Count!=0 
                        && B[i] - B[aliveFishes.Peek()] == -1 
                        && A[aliveFishes.Peek()] < A[i])  
               { aliveFishes.Pop(); }

               if (aliveFishes.Count !=0) 
               { if(B[i] - B[aliveFishes.Peek()] != -1) aliveFishes.Push(i); }

               else { aliveFishes.Push(i); }

        }

  }

  return aliveFishes.Count;

    }

}

This test took me a while, even though it is marked as 'easy'. I think because initially I tried without using a Stack.

Also because i din't read it throughly and missed the detail that while comparing two fishes, the first fish needs to have direction 1 and the second direction 0, and not 0-1.

The solution takes the first fish and pushes into the stack (as this is empty).

Then with the second and following fishes, it checks three possibilities:

• While the stack is not empty, if the direction of the fish is 1 and the direction of the last fish in the stack is 0 (aliveFishes.Peek()) and the size of the fish is bigger that the last fish in the stack, the we pop (delete) the last fish in the stack (as it has been eaten).
• If the stack is not empty, and the direction of the fish and the last fish of the stack is not the right one (gets to live) we push the fish into the stack.
• if above condition doesn't occur, so the stack is empty, we push the fish (it won't be eaten yet).

For more information about Stack follow the link:

msdn -> stack class and methods

CODILITY - LESSON 4 - NumberOfDiscIntersections

PROBLEM:

We draw N discs on a plane. The discs are numbered from 0 to N − 1. A zero-indexed array A of N non-negative integers, specifying the radiuses of the discs, is given. The J-th disc is drawn with its center at (J, 0) and radius A[J].

We say that the J-th disc and K-th disc intersect if J ≠ K and the J-th and K-th discs have at least one common point (assuming that the discs contain their borders).

The figure below shows discs drawn for N = 6 and A as follows:

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

There are eleven (unordered) pairs of discs that intersect, namely:

• discs 1 and 4 intersect, and both intersect with all the other discs;
• disc 2 also intersects with discs 0 and 3.

Write a function:

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

that, given an array A describing N discs as explained above, returns the number of (unordered) pairs of intersecting discs. The function should return −1 if the number of intersecting pairs exceeds 10,000,000.

Given array A shown above, the function should return 11, as explained above.

Assume that:

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

SOLUTION (93% score, time complexity O(N*log(N)) or O(N)) 
(click here to go to codility.com and see test results)

using System; using System.Collections.Generic; class Solution { public int solution(int[] A) { int N = A.Length; long [] AX = new long[N]; long [] AY = new long[N]; for (int i = 0; i < N; i++) { AX[Math.Max(0, i - A[i])]++; AY[Math.Min(N-1, i + A[i])]++; } long result = 0; long discsAtIndex = 0; for (int i = 0; i <N; i++) { if (AX[i] > 0) { result += discsAtIndex * AX[i] + (AX[i] * (AX[i] - 1) / 2); discsAtIndex += AX[i]; } discsAtIndex -= AY[i]; } if (result <= 10000000) return (int) result; else return -1; } }

This solution fails one test;

overflow arithmetic overflow tests	0.055 s	RUNTIME ERROR tested program terminated unexpectedly
stderr: Unhandled Exception: System.IndexOutOfRangeException: Array index is out of range. at Solution.solution (System.Int32[]

The solution is easier to understand if you see each pair XY as the start and end points of a line. You would be counting how many lines are at each index.

The array AX counts how many times a line (or circle) starts before or at the index. I.e. at position 0, 4 lines (or circles) have their starting point before or at 0.

The array AY counts how many times a line (or circle) ends at the index. I.e. at position 0 no line (or circle) ends there. At position 1, one line (or circle) ends.

There are two counts; the int result (which will be the answer) and we also need to count how many lines(discs) are at each index while we loop.

For this one, I had to check some forums in order to get the result count working properly,  as i wasn't accounting for pairs already counted in the result variable ((AX[i] * (AX[i] - 1) / 2);)

PR

CODILITY - LESSON 4 - Distinct

PROBLEM:

Write a function

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

that, given a zero-indexed array A consisting of N integers, returns the number of distinct values in array A.

Assume that:

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

For example, given array A consisting of six elements such that:

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

the function should return 3, because there are 3 distinct values appearing in array A, namely 1, 2 and 3.

Complexity:

• expected worst-case time complexity is O(N*log(N));
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

MY SOLUTION (100% score, time complexity O(N) or O(N*log(N)))

(codility.com click here to see test results)

class Solution { public int solution(int[] A) { int [] newA = A.Distinct().ToArray(); if (A.Length <=0) return 0; else return newA.Length; } }

Taking advantage .NET libraries and the methods already built-in.

PR