Test results - Codility

Tasks Details

easy

1. CountDistinctSlices

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

Task Score

100%

Correctness

100%

Performance

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:

function solution(M, 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 JavaScript

Time spent on task 2 minutes

Notes

not defined yet

Code: 13:11:11 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int M, int[] A) {
        // write your code in Java SE 8
    }
}

Code: 13:11:13 UTC, js, autosave

show code in pop-up

1 2 3 4 5 6

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(M, A) {
    // write your code in JavaScript (Node.js 8.9.4)
}

Code: 13:11:17 UTC, js, autosave

show code in pop-up

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

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(M, A) {
    // write your code in JavaScript (Node.js 8.9.4)
    let sum = 0;
    let front = 0;
    let back = 0;
    const seen = new Array(M+1).fill(false);
    while (front < M-1 && back < M-1){
        while (front < M-1 && seen[A[front]] !== true){
            sum += (front-back+1);
            seen[A[front]] = true;
            front += 1;
        }
        while (A[back] !== A[front]){
            seen[A[back]] = false;
            back += 1;
        }
        seen[A[back]] = false;
        back += 1;
    }           
    return Math.min(sum, 1000000000);
}

Code: 13:11:22 UTC, js, verify, result: Passed

show code in pop-up

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

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(M, A) {
    // write your code in JavaScript (Node.js 8.9.4)
    let sum = 0;
    let front = 0;
    let back = 0;
    const seen = new Array(M+1).fill(false);
    while (front < M-1 && back < M-1){
        while (front < M-1 && seen[A[front]] !== true){
            sum += (front-back+1);
            seen[A[front]] = true;
            front += 1;
        }
        while (A[back] !== A[front]){
            seen[A[back]] = false;
            back += 1;
        }
        seen[A[back]] = false;
        back += 1;
    }           
    return Math.min(sum, 1000000000);
}

Analysis

expand all Example tests

▶

example
example test

✔

0.072 s

expand all User tests

▶

test_data1

✔

0.072 s

OK
function result: 0

User test case 1:

[0, []]

Code: 13:12:07 UTC, js, verify, result: Passed

show code in pop-up

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

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(M, A) {
    // write your code in JavaScript (Node.js 8.9.4)
    let sum = 0;
    let front = 0;
    let back = 0;
    const seen = new Array(M+1).fill(false);
    while (front < M-1 && back < M-1){
        while (front < M-1 && seen[A[front]] !== true){
            sum += (front-back+1);
            seen[A[front]] = true;
            front += 1;
        }
        while (A[back] !== A[front]){
            seen[A[back]] = false;
            back += 1;
        }
        seen[A[back]] = false;
        back += 1;
    }           
    return Math.min(sum, 1000000000);
}

Analysis

expand all Example tests

▶

example
example test

✔

0.072 s

expand all User tests

▶

test_data1

✔

0.072 s

OK
function result: 0

User test case 1:

[0, [0]]

Code: 13:12:37 UTC, js, autosave

show code in pop-up

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

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(M, A) {
    // write your code in JavaScript (Node.js 8.9.4)
    let sum = 0;
    let front = 0;
    let back = 0;
    const seen = new Array(M+1).fill(false);
    while (front <  && back < M-1){
        while (front < M-1 && seen[A[front]] !== true){
            sum += (front-back+1);
            seen[A[front]] = true;
            front += 1;
        }
        while (A[back] !== A[front]){
            seen[A[back]] = false;
            back += 1;
        }
        seen[A[back]] = false;
        back += 1;
    }           
    return Math.min(sum, 1000000000);
}

Code: 13:12:48 UTC, js, verify, result: Passed

show code in pop-up

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

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(M, A) {
    // write your code in JavaScript (Node.js 8.9.4)
    let sum = 0;
    let front = 0;
    let back = 0;
    const seen = new Array(M+1).fill(false);
    while (front < A.length && back < A.length){
        while (front < A.length && seen[A[front]] !== true){
            sum += (front-back+1);
            seen[A[front]] = true;
            front += 1;
        }
        while (A[back] !== A[front]){
            seen[A[back]] = false;
            back += 1;
        }
        seen[A[back]] = false;
        back += 1;
    }           
    return Math.min(sum, 1000000000);
}

Analysis

expand all Example tests

▶

example
example test

✔

0.076 s

expand all User tests

▶

test_data1

✔

0.072 s

OK
function result: 1

User test case 1:

[0, [0]]

Code: 13:12:52 UTC, js, verify, result: Passed

show code in pop-up

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

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(M, A) {
    // write your code in JavaScript (Node.js 8.9.4)
    let sum = 0;
    let front = 0;
    let back = 0;
    const seen = new Array(M+1).fill(false);
    while (front < A.length && back < A.length){
        while (front < A.length && seen[A[front]] !== true){
            sum += (front-back+1);
            seen[A[front]] = true;
            front += 1;
        }
        while (A[back] !== A[front]){
            seen[A[back]] = false;
            back += 1;
        }
        seen[A[back]] = false;
        back += 1;
    }           
    return Math.min(sum, 1000000000);
}

Analysis

expand all Example tests

▶

example
example test

✔

0.072 s

expand all User tests

▶

test_data1

✔

0.072 s

OK
function result: 1

User test case 1:

[0, [0]]

Code: 13:12:54 UTC, js, final, score: 100

show code in pop-up

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

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(M, A) {
    // write your code in JavaScript (Node.js 8.9.4)
    let sum = 0;
    let front = 0;
    let back = 0;
    const seen = new Array(M+1).fill(false);
    while (front < A.length && back < A.length){
        while (front < A.length && seen[A[front]] !== true){
            sum += (front-back+1);
            seen[A[front]] = true;
            front += 1;
        }
        while (A[back] !== A[front]){
            seen[A[back]] = false;
            back += 1;
        }
        seen[A[back]] = false;
        back += 1;
    }           
    return Math.min(sum, 1000000000);
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N)

expand all Example tests

▶

example
example test

✔

0.072 s

expand all Correctness tests

▶

single
single element

✔

0.076 s

0.072 s

▶

double
double elements

✔

0.076 s

▶

simple1
first simple test

✔

0.072 s

▶

simple2
second simple test

✔

0.072 s

▶

small_random
small random test, length = 100

✔

0.072 s

expand all Performance tests

▶

medium_random
medium random test, length = 500

✔

0.072 s

▶

large
large tests, length = ~100,000

✔

0.108 s

▶

large_range
large range tests, length = ~100,000

✔

0.120 s

0.100 s

▶

large_random
large random tests, length = ~100,000

✔

0.116 s

0.112 s

▶

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

✔

0.104 s

0.116 s