Ok, this is first interesting one. The concept goes like this. We iterate through input array and increase a value for element in counterArray. Elements in counterArray represents number of repetitions in inputArray of the value of index in counterArray. We intuitively iterate through inputArray until we get to element with value of N+1. Then reset Read More …
Month: August 2016
PermCheck Codility JAVA solution (100/100)
This task we can solve the similar way as PermMissingElem. First create an array of prefix sums and calculate the sum of elements in array and expected sum of elements. Subtracting those two gives the result.
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 |
// Result: 100/100 public static int solution_4_PermCheck(int[] A) { int sumOfElements = 0; int expectedSumOfElements = 0; int[] countArray = new int[A.length + 1]; for (int i = 0; i < A.length; i++) { if (A[i] >= countArray.length) return 0; if (countArray[A[i]] != 0) return 0; countArray[A[i]]++; sumOfElements += A[i]; expectedSumOfElements += i + 1; } if (sumOfElements == expectedSumOfElements) return 1; else return 0; } |
FrogRiverOne Codility JAVA solution (100/100)
Concept here is to create a counter with number of jumps needed to cross the river and an array that is long as a river with initialed zeros. When the leaf falls on a specific place, we check if the the leaf already fell to that spot and if not we decrease counter. When counter hits Read More …
TapeEquilibrium Codility JAVA solution (100/100)
This task can be easily done with prefix sums. In first for loop we create the sumArray which contains sum of all elements from A[1] to A[i]. After that, we iterate through sumArray. In position i, the element sumArray[i] tells us sum of elements from A[1] to A[i] and if we do sumArray[lastElement] – sumArray[i] we Read More …
PermMissingElem Codility JAVA solution (100/100)
Since the numbers in array are starting from 1 we can get the sum of all elements in array and subtract it from expected sum of elements if there wasn’t missing any. That should give us the element missing.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Result: 100/100 public static int solution_3_PermMissingElem(int[] A) { if (A.length == 0) return 1; int sumOfAllNumbers = 0; for (int num : A) sumOfAllNumbers += num; long N = A.length; long expectedSumOfAllNumbers = ((N + 1)*(N + 2))/2; long missingNumber = expectedSumOfAllNumbers - sumOfAllNumbers; return (int) missingNumber; } |
FrogJump Codility JAVA solution (100/100)
The frog wants to get on the other side of the road and she needs (y – x)/d jumps to get there. Simple as that. Since that can be decimal number we need to check if it needs to be rounded on lower or greater number. And that’s it. 🙂
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Result: 100/100 public static int solution_3_FrogJmp(int x, int y, int d) { double numOfJumpsF = (double)(y - x)/d; int roundNumOfJumps = (int) Math.round(numOfJumpsF); double restOfNumOfJumps = numOfJumpsF; if (roundNumOfJumps > 1) restOfNumOfJumps = numOfJumpsF % roundNumOfJumps; if (restOfNumOfJumps > 0 && restOfNumOfJumps < 0.5) roundNumOfJumps++; return roundNumOfJumps; } |