Codility solutions - lesson2, exercise: MissingInteger

Content of Codility exercise:

Write a function:

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

that, given a non-empty zero-indexed array A of N integers, returns the minimal positive integer that does not occur in A.

For example, given:

  A[0] = 1
  A[1] = 3
  A[2] = 6
  A[3] = 4
  A[4] = 1
  A[5] = 2
the function should return 5.

Assume that:

N is an integer within the range [1..100,000];
each element of array A is 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.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

public int solution(int[] A) { //tmp array to store each number from A on position equal its number minus 1 int tmpB[] = new int[A.length]; int maxElement = 0; for (int i=0; i<A.length; i++){ //only element lager than zero and smaller than A size can be considered if (A[i] <= A.length && A[i]>0){ tmpB[A[i]-1] = A[i]; } } //if tmpB array contains zero element the solution will be index of mentioned element increased by 1 //if tmpB array doesn't contain zero element solution will be th biggest element increased by 1 for(int i = 0; i<tmpB.length; i++){ if (tmpB[i] == 0){ return i+1; } if (maxElement < tmpB[i]){ maxElement = tmpB[i]; } } return maxElement+1; }

Codility solutions - lesson2, exercise: FrogRiverOne

Find the earliest time when a frog can jump to the other side of a river.
Content:

A small frog wants to get to the other side of a river. The frog is currently located at position 0, and wants to get to position X. Leaves fall from a tree onto the surface of the river.

You are given a non-empty zero-indexed array A consisting of N integers representing the falling leaves. A[K] represents the position where one leaf falls at time K, measured in minutes.

The goal is to find the earliest time when the frog can jump to the other side of the river. The frog can cross only when leaves appear at every position across the river from 1 to X.

For example, you are given integer X = 5 and array A such that:

  A[0] = 1
  A[1] = 3
  A[2] = 1
  A[3] = 4
  A[4] = 2
  A[5] = 3
  A[6] = 5
  A[7] = 4
In minute 6, a leaf falls into position 5. This is the earliest time when leaves appear in every position across the river.

Write a function:

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

that, given a non-empty zero-indexed array A consisting of N integers and integer X, returns the earliest time when the frog can jump to the other side of the river.

If the frog is never able to jump to the other side of the river, the function should return −1.

For example, given X = 5 and array A such that:

  A[0] = 1
  A[1] = 3
  A[2] = 1
  A[3] = 4
  A[4] = 2
  A[5] = 3
  A[6] = 5
  A[7] = 4
the function should return 6, as explained above.

Assume that:

N and X are integers within the range [1..100,000];
each element of array A is an integer within the range [1..X].
Complexity:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(X), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

public int solution(int X, int[] A) { //To check if all necessary Leaves already lies on water I decided to count sum of every number from 0 to X int XElementsSum = 0; //if some value in tmpB array isn't equal zero, it is mean that leave already lies on water int[] tmpB = new int[X]; int finalSum = 0; for (int i = 0; i<=X; i++){ XElementsSum = XElementsSum + i; } for (int i = 0; i < A.length ; i++){ //finalSum will be increased only when leave doesn't lie yet on current position if (A[i] <= X && tmpB[A[i]-1] == 0){ tmpB[A[i]-1] = A[i]; finalSum = finalSum + A[i]; } //if finalSum is equal XElementsSum, it mean that all necessary leaves already lies on water if (finalSum == XElementsSum){ return i; } } return -1; }

Codility solutions - lesson2, exercise: PermCheck

Check whether array A is a permutation.

Content of Codility exercise:

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

A permutation is a sequence containing each element from 1 to N once, and only once.

For example, array A such that:

    A[0] = 4
    A[1] = 1
    A[2] = 3
    A[3] = 2
is a permutation, but array A such that:

    A[0] = 4
    A[1] = 1
    A[2] = 3
is not a permutation, because value 2 is missing.

The goal is to check whether array A is a permutation.

Write a function:

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

that, given a zero-indexed array A, returns 1 if array A is a permutation and 0 if it is not.

For example, given array A such that:

    A[0] = 4
    A[1] = 1
    A[2] = 3
    A[3] = 2
the function should return 1.

Given array A such that:

    A[0] = 4
    A[1] = 1
    A[2] = 3
the function should return 0.

Assume that:

N is an integer within the range [1..100,000];
each element of array A is an integer within the range [1..1,000,000,000].
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.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

public int solution(int[] A) { int N = A.length; //create tmp array to store information about each number occurrence int tmbB[] = new int[A.length]; int element = 0; for (int i = 0; i < A.length; i++){ element = A[i]; //if element is greater than array A length it is obvious that A isn't permutation if (element> N){ return 0; } tmbB[element-1]++; } //index where number in array is equal zero, is our missing element //and array A isn't permutation if (isContainZeroElement(tmbB)){ return 0; }else { return 1; } } private boolean isContainZeroElement(int [] B){ for (int element: B){ if (element == 0){ return true; } } return false; }

Codility solutions - lesson1, exercise: TapeEquilibrium

Content of Codility exercise:

A non-empty zero-indexed array A consisting of N integers is given. Array A represents numbers on a tape.

Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].

The difference between the two parts is the value of: |(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|

In other words, it is the absolute difference between the sum of the first part and the sum of the second part.

For example, consider array A such that:

  A[0] = 3
  A[1] = 1
  A[2] = 2
  A[3] = 4
  A[4] = 3
We can split this tape in four places:

P = 1, difference = |3 − 10| = 7
P = 2, difference = |4 − 9| = 5
P = 3, difference = |6 − 7| = 1
P = 4, difference = |10 − 3| = 7
Write a function:

int solution(int A[], int N);

that, given a non-empty zero-indexed array A of N integers, returns the minimal difference that can be achieved.

For example, given:

  A[0] = 3
  A[1] = 1
  A[2] = 2
  A[3] = 4
  A[4] = 3
the function should return 1, as explained above.

Assume that:

N is an integer within the range [2..100,000];
each element of array A is an integer within the range [−1,000..1,000].
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).

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

public int solution(int[] A) { //initialize variables int minDifference = 0; int divisionNumber = A.length - 1; int leftSum = 0; int rightSum = 0; //calculate table right, left sum and first difference after first division for (int i = 1; i< A.length ; i++){ rightSum = rightSum + A[i]; } leftSum = A[0]; minDifference = Math.abs(leftSum - rightSum); //condition to secure if table A has only two elements if (divisionNumber > 1){ //walking across table A and counting needed variables for (int p = 2; p<=divisionNumber ; p ++){ leftSum = leftSum + A[p-1]; rightSum = rightSum - A[p-1]; int tmpminDifference = Math.abs(leftSum - rightSum); if (minDifference > tmpminDifference){ minDifference = tmpminDifference; } } return minDifference; }else { return minDifference; } }

Codility solutions - lesson1, exercise: PermMissingElem

Content of Codility excercise:

A zero-indexed array A consisting of N different integers is given.
The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

Your goal is to find that missing element.

Write a function:

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

that, given a zero-indexed array A, returns the value of the missing element.

For example, given array A such that:

  A[0] = 2
  A[1] = 3
  A[2] = 1
  A[3] = 5
the function should return 4, as it is the missing element.

Assume that:

N is an integer within the range [0..100,000];
the elements of A are all distinct;
each element of array A is an integer within the range [1..(N + 1)].
Complexity:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.

Solution:

    public int solution(int[] A) {
        //Create tmp table with only elements equal 0,
        int []tmpB = new int[A.length+1];
        //Store in tmp table all element from table A.
        for (int element: A){
            tmpB[element-1] = element;
        }
        int missingElement = 1;
        int i = 0;
        // Now Tmp table contain one integer equal 0. Our solution will be index increased by 1 of such integer
        while (missingElement != 0){
            missingElement = tmpB[i];
            i++;
        }
        return i;
    }

Codility solutions - lesson1, exercise: FrogJmp

Content of Codility excercise:


A small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to a position greater than or equal to Y.
The small frog always jumps a fixed distance, D.

Count the minimal number of jumps that the small frog must perform to reach its target.

Write a function:

class Solution { public int solution(int X, int Y, int D); }

that, given three integers X, Y and D, returns the minimal number of jumps from position X to a position equal to or greater than Y.

For example, given:

  X = 10
  Y = 85
  D = 30
the function should return 3, because the frog will be positioned as follows:

after the first jump, at position 10 + 30 = 40
after the second jump, at position 10 + 30 + 30 = 70
after the third jump, at position 10 + 30 + 30 + 30 = 100
Assume that:

X, Y and D are integers within the range [1..1,000,000,000];
X ≤ Y.
Complexity:

expected worst-case time complexity is O(1);
expected worst-case space complexity is O(1).

Solution:

    public int solution(int X, int Y, int D) {
        if ((Y-X)%D == 0){
            return (Y-X)/D;
        }else {
            return (Y-X)/D + 1;
        }
    }

Remote debug Windows-based Tomcat service

To enable remote debugging in a Windows-based Tomcat service. Please follow the following steps to add debug settings to a Tomcat service.

1. From the command line(run as administrator) call the following command
   
   


   %TOMCAT_HOME%/bin/tomcat6w.exe //ES//<ServiceName>
   
   where <ServiceName> is actual windows service name
   *A properties dialog box pops out.
2. Navigate to the Java tab and add the following entries in the Java Options section
   
   
   -Xdebug

   -Xrunjdwp:transport=dt_socket,address=5005,server=y,suspend=n

After restarting the service you'll be able to run remote debug on port 5005.