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:

class Solution { public int solution(int M, 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 Java 8

Time spent on task 1 minutes

Notes

not defined yet

Task timeline

Code: 10:02:11 UTC, java, 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

// 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
        boolean chk[] = new boolean[M+1];
        int ans = 0, right = 0;
        int n = A.length;
        
        for(int left=0;left<n;left++) {
            // 중복 원소 나올때까지 right 증가시키며 cnt
            while(right < A.length && !chk[A[right]]) {
                ans += (right-left+1);
                chk[A[right]] = true;
                right++;
                
                if(ans >= 1000000000) {
                    return 1000000000;
                }
            }

            chk[A[left]] = false; // left 끝나면 제외시킴

            if(ans >= 1000000000) {
                return 1000000000;
            }
        }

        return ans;
    }
}

Analysis

▶

example
example test

✔

Code: 10:02:17 UTC, java, 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

// 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
        boolean chk[] = new boolean[M+1];
        int ans = 0, right = 0;
        int n = A.length;
        
        for(int left=0;left<n;left++) {
            // 중복 원소 나올때까지 right 증가시키며 cnt
            while(right < A.length && !chk[A[right]]) {
                ans += (right-left+1);
                chk[A[right]] = true;
                right++;
                
                if(ans >= 1000000000) {
                    return 1000000000;
                }
            }

            chk[A[left]] = false; // left 끝나면 제외시킴

            if(ans >= 1000000000) {
                return 1000000000;
            }
        }

        return ans;
    }
}

Analysis

▶

example
example test

✔

Code: 10:02:21 UTC, java, 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

// 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
        boolean chk[] = new boolean[M+1];
        int ans = 0, right = 0;
        int n = A.length;
        
        for(int left=0;left<n;left++) {
            // 중복 원소 나올때까지 right 증가시키며 cnt
            while(right < A.length && !chk[A[right]]) {
                ans += (right-left+1);
                chk[A[right]] = true;
                right++;
                
                if(ans >= 1000000000) {
                    return 1000000000;
                }
            }

            chk[A[left]] = false; // left 끝나면 제외시킴

            if(ans >= 1000000000) {
                return 1000000000;
            }
        }

        return ans;
    }
}

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

✔