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

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

CODILITY - LESSON 4 - Triangle

PROBLEM :

A zero-indexed array A consisting of N integers is given. A 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] = 20

Triplet (0, 2, 4) is triangular.

GOOD SOLUTION (93% score, time complexity O(N*log(N))

(codility.com click here to see breakdown of the test results)

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

Array.Sort(A); if (A.Length <3) return 0; for (int i=0 ; i<A.Length-2 ; i++) { if (A[i] + A[i+1] > A[i+2] ) {return 1; break; } } return 0; } }

I made one mistake here which I realised only once all the test results were ran: I didn't account if the triplet is formed by 3 maxValue integers (C# will wraparound the result of the sum of two maxValues).

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

(codility.com click here to see breakdown of the test results)

class Solution { public int solution(int[] A) { Array.Sort(A); if (A.Length <3) return 0; for (int i=0 ; i<A.Length-2 ; i++) { if (A[i] + A[i+1] > A[i+2] ) {

return 1; break; } if (A[i] == A[i+2] && 

A[i+2] == A[i+1] && 

A[i] == Int32.MaxValue) {

return 1; break; } } return 0; } }

PR

CODILITY - LESSON 4 - MaxProductOfThree

PROBLEM (codility.com - click here to see)

A non-empty zero-indexed array A consisting of N integers is given. The product of triplet (P, Q, R) equates to A[P] * A[Q] * A[R] (0 ≤ P < Q < R < N).

For example, array A such that:

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

contains the following example triplets:

• (0, 1, 2), product is −3 * 1 * 2 = −6
• (1, 2, 4), product is 1 * 2 * 5 = 10
• (2, 4, 5), product is 2 * 5 * 6 = 60

Your goal is to find the maximal product of any triplet.

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

class Solution { public int solution(int[] A) { Array.Sort (A); int a=0; if (A[0]<0 && A[1] <0) a = A[0]*A[1]*A[A.Length-1]; int b = A[A.Length-1]*A[A.Length-2]*A[A.Length-3]; if (a >b && (A[0]<0 && A[1] <0)) return a; else return b; } }

It first sorts the array (from min element to max element).

(Array.Sort (A) => -3,-2,1,2,5,6)

There is two possibilities:

• The first two elements are negative. Then we need to check if the triplet of those two elements and the last element in the array is > the product of the last three elements.
• Any other situation, the maximal product is the product of the last three elements.

PR

codility.com - result