Codility lessons solutions https://codility.com/programmers/lessons

1-Iterations.java

package com.example;

public class Iterations {

    static int solution_BinaryGap(int N) {
        if (N < 2) return 0;
        boolean isInGap = false;
        int maxGap = 0, currentGap = 0;
        for (int i = Integer.SIZE - 1; i >= 0; --i) {
            if ((N & (1 << i)) != 0) {
                isInGap = true;
                if (currentGap > maxGap) maxGap = currentGap;
                currentGap = 0;
            } else if (isInGap) {
                currentGap++;
            }
        }
        return maxGap;
    }

    static void test(int i, int expected) {
        int solution = solution(i);
        System.out.println(i + ": " + solution + (expected == solution ? "" : ", expecting " + expected));
    }

    public static void main(String[] args) {
        test(0, 0);
        test(2, 0);
        test(1041, 5);
        // Trailing 0
        test(6, 0); // 110_2
        test(328, 2); // 101001000_2
        // Power of 2
        test(5, 1); // 101_2
        test(16, 0); // 2**4
        test(1024, 0); // 2**10
    }
}

2-Arrays.java

package com.example;

import java.util.Arrays;

public class Arrays {

    static int solution_OddOccurrencesInArray(int[] A) {
        int sortedA[] = new int[A.length];
        int i;
        for (i = A.length - 1; i >= 0; --i) sortedA[i] = A[i];

        Arrays.sort(sortedA);
        int currentValue = -1, nOccur = 0;
        i = 0;
        do {
            if (currentValue != sortedA[i]) {
                if (nOccur % 2 == 1) return currentValue;
                currentValue = sortedA[i];
                nOccur = 1;
            } else {
                nOccur++;
            }
            i++;
        } while (i < A.length);
        return currentValue;
    }

    static void test_OddOccurrencesInArray(int[] i, int expected) {
        int solution = solution(i);
        System.out.println(Arrays.toString(i) + ": " + solution
                + (expected == solution ? "" : ", expecting " + expected));
    }

    public static void main_OddOccurrencesInArray(String[] args) {
        test(new int[] {9, 3, 9, 3, 9, 7, 9}, 7);
        test(new int[] {9}, 9);
        test(new int[] {7, 9, 9}, 7);
        test(new int[] {9, 7, 7}, 9);
    }

    static int[] solution_CyclicRotation(int[] A, int K) {
        if (K == 0) return A;
        int[] rotatedArr = new int[A.length];
        int newIdx = K;
        for (int i = 0; i < A.length; ++i) {
            if (newIdx >= A.length)
                newIdx = newIdx % A.length;
            rotatedArr[newIdx] = A[i];
            newIdx++;
        }
        return rotatedArr;
    }

    static void test_CyclicRotation(int[] i, int k) {
        int[] solution = solution(i, k);
        System.out.println(Arrays.toString(i) + " " + k + ": " + Arrays.toString(solution));
    }

    public static void main_CyclicRotation(String[] args) {
        test_CyclicRotation(new int[] {1, 2, 3, 4}, 3);
        test_CyclicRotation(new int[] {1, 2}, 5);
        test_CyclicRotation(new int[] {1}, 1);
    }
}

3-TimeComplexity.java

import java.util.*;


class TimeComplexity {

    /*
     * See https://codility.com/demo/results/training9USUWJ-EGT/
     *
     * Difficulties:
     * - long for big numbers
     * - sum(1..n) = n * (n+1) / 2 and not 2^n-1 (always check for big samples like [1, 2, 3, 4, 5, 6, 7])
     */
    public int solution_PermMissingElem(int[] A) {
        long length = A.length + 1;

        long sum = length * (length + 1) / 2;
        long currentSum = 0;
        for (int i = A.length - 1; i >= 0; --i) currentSum += A[i];

        // Missing 1
        if (currentSum == sum + 1) return 1;
        // Missing next element
        if (sum == currentSum) return (int) length + 1;
        // Missing an element between 1 and last element
        return (int) (sum - currentSum);
    }

    // See https://codility.com/demo/results/trainingBH2V3E-C7Z/
    public int solution_FrogJmp(int X, int Y, int D) {
        int distance = Y - X;
        return distance / D + (distance % D == 0 ? 0 : 1);
    }

    
    // https://codility.com/demo/results/training7DN2FZ-XD4/
    public int solution_TapeEquilibrium_83Percent(int[] A) {
        long sumLeft = 0;
        for (int i = 0; i < A.length; ++i) {
            sumLeft += A[i];
        }
        if (sumLeft == 0) return 0;

        long minDiff = Long.MAX_VALUE, sumRight = 0, difference;
        for (int i = A.length - 1; i >= 0 && minDiff > 0; --i) {
            sumLeft -= A[i];
            sumRight += A[i];
            difference = sumLeft < sumRight ? sumRight - sumLeft : sumLeft - sumRight;
            minDiff = minDiff > difference ? difference : minDiff;
        }
        return (int) minDiff;
    }
}

4-CountingElements.java

class CountingElements {
    
    // See https://codility.com/demo/results/trainingZ495MU-C3Y/
    public int solutionFrogRiverOne(int X, int[] A) {
        int[] firstOcc = new int[X];
        for (int i = 0; i < X; i++) firstOcc[i] = -1;
        
        int foundPositions = 0, val;
        for (int i = 0; i < A.length; ++i) {
            val = A[i];
            if (val <= X && firstOcc[val - 1] == -1) {
                foundPositions++;
                firstOcc[val - 1] = i;
            }
            if (foundPositions == X) return i;
        }
        return -1;
    }

    // See https://codility.com/demo/results/training7K7XUD-8ZE/
    public int[] solutionMaxCounter(int N, int[] A) {
        int[] counters = new int[N];
        for (int i = 0; i < N; ++i) counters[i] = 0;

        int val, max = 0, lastMaxCounterOp = 0;
        for (int i = 0; i < A.length; ++i) {
            val = A[i];
            if (val <= N) {
                // Increment
                counters[val - 1] = 1 + Math.max(lastMaxCounterOp, counters[val - 1]);
                if (counters[val - 1] > max)
                    max = counters[val - 1];
            } else if (val == N + 1)  {
                // Max counter
                lastMaxCounterOp = max;
            }
        }
        // Apply remaining max counter op
        for (int j = 0; j < N; j++)
            counters[j] = Math.max(lastMaxCounterOp, counters[j]);
        return counters;
    }

}

5-PrefixSums.java

class PrefixSums {

    public int solution_CountDiv_25Percent(int A, int B, int K) {
        return (int) ((((long) B - A) + (K - 1)) / K);
    }

    // See https://codility.com/demo/results/training6F7M6W-A8J/
    // for the input [11, 14, 2] the solution returned a wrong answer (got 1 expected 2).
    public int solution_CountDiv_75Percent(int A, int B, int K) {
        return (A % K == 0 ? 1 : 0) +
                (int) (((long) B - A) / K);
    }

    // See https://codility.com/demo/results/training3UXBKB-8G9/
    public int solution_PassingCars(int[] A) {
        int nCarsToEast = 0, nPairs = 0;
        for (int i = 0; i < A.length; ++i) {
            if (A[i] == 0) {
                // East direction car
                nCarsToEast++;
            } else {
                // West direction car
                nPairs += nCarsToEast;
                // Stupid condition!!
                if (nPairs > 1000000000) return -1;
            }
        }
        return nPairs;
    }

    /**
     * See https://codility.com/demo/results/training56WUR4-U7V/
     * CAGCCTA, [2, 5, 0], [4, 5, 6] = [2, 4, 1]
     * ACGTACGTAC, [0, 1, 9, 0, 1, 3], [0, 1, 9, 9, 3, 6] = [1, 2, 2, 1, 3, 1]
     */
    public int[] solution_GenomicRangeQuery_87Percent(String S, int[] P, int[] Q) {
        public int[] solution(String S, int[] P, int[] Q) {
        char[] C = S.toCharArray();
        int length = C.length;

        int[] valueChanges = new int[length];
        int lastValue = -1, lastValueIdx = 0, val;
        for (int i = 0; i < length; ++i) {
            val = nucleotideToImpactFactor(C[i]);
            if (val != lastValue) {
                // New last value
                lastValue = val;
                lastValueIdx = i;
            }
            // Store idx of the first same value found in this set
            valueChanges[i] = lastValueIdx;
        }

        int[] results = new int[P.length];
        int minVal, idx;
        for (int i = 0; i < P.length; ++i) { // For M queries
            // Take value of last set idx
            idx = Q[i];
            minVal = Integer.MAX_VALUE;
            do {
                minVal = Math.min(minVal, nucleotideToImpactFactor(C[idx]));
                idx = Math.min(idx - 1, valueChanges[idx]);
            } while (idx > P[i]);
            results[i] = Math.min(minVal, nucleotideToImpactFactor(C[P[i]]));
        }
        return results;
    }
    public int nucleotideToImpactFactor(char c) {
        return c == 'A' ? 1 : c == 'C' ? 2 : c == 'G' ? 3 : 4;
    }

    // TODO: MinAvgTwoSlice
}