Test results - Codility

Tasks Details

easy

1. CountDistinctSlices

Count the number of distinct slices (containing only unique numbers).

100%

An integer M and a non-empty array A consisting of N non-negative integers are given. All integers in array A are less than or equal to M.

A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The slice consists of the elements A[P], A[P + 1], ..., A[Q]. A distinct slice is a slice consisting of only unique numbers. That is, no individual number occurs more than once in the slice.

For example, consider integer M = 6 and array A such that:

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

There are exactly nine distinct slices: (0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2), (3, 3), (3, 4) and (4, 4).

The goal is to calculate the number of distinct slices.

Write a function:

int solution(int M, vector<int> &A);

that, given an integer M and a non-empty array A consisting of N integers, returns the number of distinct slices.

If the number of distinct slices is greater than 1,000,000,000, the function should return 1,000,000,000.

For example, given integer M = 6 and array A such that:

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

the function should return 9, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

M is an integer within the range [0..100,000];

each element of array A is an integer within the range [0..M].

Solution

Programming language used C++

Total time used 1 minutes

Effective time used 1 minutes

Notes

not defined yet

Task timeline

Code: 01:06:44 UTC, cpp, verify, result: Passed

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 31 32 33 34 35 36

#include <unordered_map>

int solution(int M, vector<int> &A) {
    const int MAX_RESULT = 1'000'000'000;

    std::unordered_map<int, int> index_lookup;

    int result = 0;

    int begin = -1;
    int end = 0;

    while (end < A.size()) {

        int current = A[end];
        int previous_position = -1;

        if(index_lookup.find(current) != index_lookup.end()) {
            previous_position = index_lookup[current];
        }

        begin = std::max(begin, previous_position);

        result += end - begin;

        if (result > MAX_RESULT) {
            return MAX_RESULT;
        }

        index_lookup[current] = end;

        end++;
    }

    return result;
}

Analysis

▶

example
example test

✔

Code: 01:06:49 UTC, cpp, verify, result: Passed

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 31 32 33 34 35 36

#include <unordered_map>

int solution(int M, vector<int> &A) {
    const int MAX_RESULT = 1'000'000'000;

    std::unordered_map<int, int> index_lookup;

    int result = 0;

    int begin = -1;
    int end = 0;

    while (end < A.size()) {

        int current = A[end];
        int previous_position = -1;

        if(index_lookup.find(current) != index_lookup.end()) {
            previous_position = index_lookup[current];
        }

        begin = std::max(begin, previous_position);

        result += end - begin;

        if (result > MAX_RESULT) {
            return MAX_RESULT;
        }

        index_lookup[current] = end;

        end++;
    }

    return result;
}

Analysis

▶

example
example test

✔

Code: 01:06:52 UTC, cpp, final, score: 100

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 31 32 33 34 35 36

#include <unordered_map>

int solution(int M, vector<int> &A) {
    const int MAX_RESULT = 1'000'000'000;

    std::unordered_map<int, int> index_lookup;

    int result = 0;

    int begin = -1;
    int end = 0;

    while (end < A.size()) {

        int current = A[end];
        int previous_position = -1;

        if(index_lookup.find(current) != index_lookup.end()) {
            previous_position = index_lookup[current];
        }

        begin = std::max(begin, previous_position);

        result += end - begin;

        if (result > MAX_RESULT) {
            return MAX_RESULT;
        }

        index_lookup[current] = end;

        end++;
    }

    return result;
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N)

▶

example
example test

✔

▶

single
single element

✔

▶

double
double elements

✔

▶

simple1
first simple test

✔

▶

simple2
second simple test

✔

▶

small_random
small random test, length = 100

✔

▶

medium_random
medium random test, length = 500

✔

▶

large
large tests, length = ~100,000

✔

▶

large_range
large range tests, length = ~100,000

✔

▶

large_random
large random tests, length = ~100,000

✔

▶

extreme_the_same
all the same elements, length = ~100,000

✔