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 - Nesting

PROBLEM:

A string S consisting of N characters is called properly nested if:

• S is empty;
• S has the form "(U)" where U is a properly nested string;
• S has the form "VW" where V and W are properly nested strings.

For example, string "(()(())())" is properly nested but string "())" isn't.

Write a function:

class Solution { public int solution(string S); }

that, given a string S consisting of N characters, returns 1 if string S is properly nested and 0 otherwise.

For example, given S = "(()(())())", the function should return 1 and given S = "())", the function should return 0, as explained above.

MY INITIAL SOLUTION (87% score, time complexity O(N))

(click here to see the full test results at codility.com)

I did this solution in few different ways and all the time got 87% overall, missing one correctness test:

negative_match invalid structure, but the number of parentheses matches

0.061 s

WRONG ANSWER got 1 expected 0

class Solution { public int solution(string S) { int l = S.Length; int count=0; if (l == 0) return 1; foreach (char c in S) { if (c == '(') count++; else count--; } if (count ==0 && S[0]=='(' && S[l-1]==')') return 1; else return 0; } }

Until I realised I wasn't taking into account strings such as "( ( ) ( ) )" which has the right amount of pairs but it is wrongly nested. After this, it took me a while to realise the silly extra line that would correct this little error...

MY IMPROVED SOLUTION (100%, time complexity O(N))

(click here to see the full test results at codility.com)

class Solution { public int solution(string S) { // write your code in C# 6.0 with .NET 4.5 (Mono) int l = S.Length; int count=0; if (l == 0) return 1; foreach (char c in S) { if (c == '(') count++; else count--; if(count <0) return 0;//CORRECTING ABOVE ERROR! } if (count ==0 && S[0]=='(' && S[l-1]==')') return 1; else return 0; } }

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