Codility Solutions

On this page I am sharing my solutions to the problem sets. They can be found here. Enjoy and share your comments!

1) Time Complexity

2) Counting Elements

3) Prefix Sums

4) Sorting

5) Stacks and Queues

6) Leader

7) Maximum Slice Problem

8) Prime and composite numbers

9) Sieve or Eratosthenes

10) Euclidean Algorithm

11) Fibonacci Numbers

12) Binary Search

13) Caterpillar method

14) Greedy algorithms

15) Dynamic Programming

16) Future Training

X) Challenges

Based on the Codility Terms of Service it is allowed to share training solutions and solutions to past challenges.

8.1.  Any Task, statement or information on the Site (including Tests Sessions and Test Session results) is confidential information. You agree not to:

(a)   disclose, publish or reproduce (including posting on any webpage or blog) such information; or

(b)   disclose to others details of a recruitment Task, ongoing monthly Challenge or ongoing competition Task (including details relating to its completion).

8.2.  This clause does not apply to: Training section of Codility service, Training Tasks and Past Challenges, their solutions and assessment results.

  • Sritharan

    Hi Martin, Yesterday I had a test in codility, i solved it but it is showing only 50% CORRECT pls help on this. It would be of great help.


    You would like to find the sentence containing the largest numberof words in some given text.

    For example given S = “We test coders. Give us a try?”, there are three sentences. “We test coders”, “Give us a try” and “”. The second sentence contains four words: “Give”, “us”, “a” and “try”. The third sentence is empty: the function should return 4 as the solution

    The answer should return the number of words in the longest sentence.
    public static void main(String args[]) {

    String string = “fdsfdsfdsf erfdsfgf. sarfsafdsf?”;



    public static int solution(String s) {

    if (s == null || s.length() == 0) {

    return 0;


    Pattern re = Pattern.compile(“[^.!?\s][^.!?]*(?:[.!?](?![‘”]?\s|$)[^.!?]*)*[.!?]?[‘”]?(?=\s|$)”, Pattern.MULTILINE | Pattern.COMMENTS);

    Matcher reMatcher = re.matcher(s);

    int max = 0;

    while (reMatcher.find()) {

    String splitarr[]=“\s+”);

    max = splitarr.length;


    return max;


    • Hey Sritharan,

      first of all. Forget regular expressions, they are extremely slow.

      Here is a short Python code that does that.

      It is still unoptimised because it creates a copy of the array, which is actually not necessary. You would be better off if you tested each character in the array for being a letter or a non-letter. Words are defined as sequences of letters. Not every non letter is a new word, sequence of non-letters does not define a new word. Sentences end with [.!?] If you manage to translate this description into code, you will solve the problem with optimal runtime.

      I won’t give you the exact code, it is probably against Codility’s copyright.

      Also, test your code against extreme cases. Does the text “” and “…” return max length 0 or 1?


      • Sritharan

        Thank You Marin, for your help. Have a great day. I see a point in your question and i solved the question exactly as per your guidance. Thanks once again.

    • Yogendra

      C# Code :

      string _myName = “My Name is Yogendra Dubey “;
      var LongestWord = _myName.Split(‘ ‘).OrderByDescending(r => r.Length).FirstOrDefault();

  • Michael Smith send me an email and I will send you a solution for codility tasks

  • Rishikesh Patil

    Hi Martin, help solving me this question.
    A non-empty zero indexed array A consisting of N non negative integers is given. Its binarian is defined as:
    pow2(K)= 2^k
    For example, the binarian of array A such that:
    A[0] = 1
    A[1] = 5
    A[2] = 4
    equals 50

    binarian (A)=pow2(A[0]) + pow2(A[1]) + pow2(A[2])
    = pow2(1) + pow2(5) + pow2(4)
    = 2 + 32 +16
    = 50
    write a function.
    class function ( public int solution ( int[] A);}
    that given an array A consisting of N non negative integers, returns the length of the shortest arraythat has the same binarian as array A.
    For example, given array A such that:
    A[0] = 1
    A[1] = 0
    A[2] = 2

    expected worse case time complexity is O(log(N))
    expected worse case space complexity is O(1)

    • Hi Rishikesh,

      I don’t solve stuff for people as it might be part of any ongoing contest or a task they have been given by their future employers. But I will tell you how to solve it.

      Do you know the Coin Counting Problem?

      The solution to your question is a variation of the CCP.
      – Use Dynamic Programming (or memoization) to speed up sub-parts of the problem.
      – iterate over all numbers up to sqrt(binarian(A))
      – sqrt(N) is generally considered to be log(N) complexity

      Example 50:
      sqrt(50) = 7.07
      7*7 + 1*1 = 50
      6*6 + 2*2 = 50
      5*5 + 5*5 = 50
      5*5 + 4*4 + 3*3 = 50

    • Raj kumar

      Hi Rishikesh Patil, did you find the solution??

  • Puneet Sindhwani

    Hi Martin

    Please let me know if following code is correct or not for finding the minimum number of students standing in a contiguous group who, after rearranging their positions, will cause the entire row to be ordered by height.

    function solution($array) {
    $newarray = $array;
    $length = count($array);
    $swaps = 0;
    $b = 0;
    for ($a = 0; $a < $length; $a++) {
    if ($array[$a] == $newarray[$b]) {
    $b = $b + 1;
    } else {
    $swaps = $swaps + 1;

    return $swaps;

    $array = array(1,2,6,5,5,8,9);

    • Let me rephrase your question: Given an array A, find the smallest non-increasing sub-array A’. The issue which that definition is, that a non-sorted sub-array could contain elements that belong to a sorted part of A. You should be able to solve the problem with a two-directional caterpillar method. It will require a few pointers but it is possible in O(n). Is it a Credit Suisse interview question?

      • Puneet Sindhwani

        It is related to clicking the pictures of students of a class standing in a row.


        1. expected worst-case time complexity is O(N*LOG(N))

        2. expected worst-case space complexity is O(N), beyond input storage

      • despina

        Hello, got the same problem, solved with caterpillar two-way method, got good results when testing with the sample array and 3 other, then.. surprise: test score: 11%.. not sure what I missed..

        • That would explain the expected O(NlogN) complexity. @puneetsindhwani:disqus does your algorithm solve the problem? If not, where is the issue?

          • despina

            Regarding @Puneet algoritm: Let’s suppose the test nonsorted array would have another element at the end with value 1.

            Comparing this array against the sorted one would return the nr of swaps equal toate the array count. The expected result though should be count-3.

          • Puneet Sindhwani

            We got the score as 0% but we don’t know the reason for this. We ran around 8 test cases including the example given and all went well. We just need to know what was wrong in the code.

          • despina

            Hello, @puneetsindhwani:disqus. Again, your algorithm doesn’t work for the following test case:
            $array = array(1,2,6,5,5,8,9,1);

            You are not returning “contiguous group who, after rearranging their positions, will cause the entire row to be ordered”, but rather compare the ordered and unordered arrays against each other. Simply adding another small value at the end of the sample array would demonstrate that.

  • pert hax

    Hi Martin,

    Can you give me a tip on how to solve this step by step? I’m not asking for solutions, just a tip or a guide. Thank you!

    A zero-indexed array A consisting of N integers is given. An equilibrium index of this array is any integer P such that 0 ≤ P < N and the sum of elements of lower indices is equal to the sum of elements of higher indices, i.e.
    A[0] + A[1] + … + A[P−1] = A[P+1] + … + A[N−2] + A[N−1].
    Sum of zero elements is assumed to be equal to 0. This can happen if P = 0 or if P = N−1.

    For example, consider the following array A consisting of N = 8 elements:

    A[0] = -1
    A[1] = 3
    A[2] = -4
    A[3] = 5
    A[4] = 1
    A[5] = -6
    A[6] = 2
    A[7] = 1
    P = 1 is an equilibrium index of this array, because:

    A[0] = −1 = A[2] + A[3] + A[4] + A[5] + A[6] + A[7]
    P = 3 is an equilibrium index of this array, because:

    A[0] + A[1] + A[2] = −2 = A[4] + A[5] + A[6] + A[7]
    P = 7 is also an equilibrium index, because:

    A[0] + A[1] + A[2] + A[3] + A[4] + A[5] + A[6] = 0
    and there are no elements with indices greater than 7.

    P = 8 is not an equilibrium index, because it does not fulfill the condition 0 ≤ P < N.

    Write a function:

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

    that, given a zero-indexed array A consisting of N integers, returns any of its equilibrium indices. The function should return −1 if no equilibrium index exists.

    For example, given array A shown above, the function may return 1, 3 or 7, 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 [−2,147,483,648..2,147,483,647].

    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.

    • Hi Pert,

      if all numbers are positive, you can have a look at this variant of the problem

      In the Codility Equi case, you can have negative values. Simply create an array with prefix sums. That can be computed in O(n) time in a single pass. Afterwards compare the sum of all elements on the left (the prefix sum) to the sum on the right (calculated from the prefix sum and the sum of all elements).