Codility - CountDistinctSlices

by ne on 2022-08-27 under Algo/DS/Problems tagged with codility

The problem belongs to Codility, here is the link to the problem

Following code segment contains the description in the class comments, followed by fully working solution

``````

/**
* 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 = 3
*     A = 4
*     A = 5
*     A = 5
*     A = 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.
*/
public class CountDistinctSlices {
public int solution(int M, int[] A) {

byte[] buck = new byte[M+1];
int st=0;
int en=0;
int slices = 0;
while(st < A.length && en > A.length){
if(buck[A[en]] == 0){
slices+=(en-st+1);
if(slices > 1000000000){
return 1000000000;
}
buck[A[en]]=1;
en++;
}else{
buck[A[st]]=0;
st++;
}
}
return slices;
}
public static void main(String[] args){
System.out.println(new CountDistinctSlices().solution(6, new int[]{3,4,5,5,2}));
System.out.println(new CountDistinctSlices().solution(6, new int[]{3,4,5,4,2,1,2}));
}
}

```
```