https://codility.com/programmers/lessons/13
An integer M and a non-empty zero-indexed 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, int A[], int N);
that, given an integer M and a non-empty zero-indexed 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.
http://www.martinkysel.com/codility-countdistinctslices-solution/
Using the caterpillar method I expand the caterpillar to the right as long as a duplicate element is found. The right side has to retract as long as this duplicate element has been eliminated from the next slice. An observation showed that the number of sub-slices is equal to front-back+1.
def solution(M, A): the_sum = 0 front = back = 0 seen = [False] * (M+1) while (front < len(A) and back < len(A)): while (front < len(A) and seen[A[front]] != True): the_sum += (front-back+1) seen[A[front]] = True front += 1 else: while front < len(A) and back < len(A) and A[back] != A[front]: seen[A[back]] = False back += 1 seen[A[back]] = False back += 1 return min(the_sum, 1000000000)
// Time--O(N) Space--O(M)
// https://codility.com/demo/results/demo724FXS-J88/
public int solution(int M, int[] A) {
int ans = 0, pre = -1;
int[] hash = new int[M + 1];
for (int i = 0; i < hash.length; i++) hash[i] = -1;
for (int i = 0; i < A.length; i++) {
if (hash[A[i]] > pre) {
pre = hash[A[i]];
}
ans += i - pre;
hash[A[i]] = i;
if (ans > 1000000000) ans = 1000000000;
}
return ans;
}
int solution(int M, int A[], int N)
{
int memsize = sizeof(int) * (M + 1);
int*found = (int*)alloca(memsize);
memset(found, 0xFF, memsize);
int r = 0; int l = -1; int cnt = 0; for ( ; r < N; r++){ if (found[A[r]] > l){ l = found[A[r]]; } cnt += r - l; found[A[r]] = r; if (cnt > 1000000000){ return 1000000000; } } return cnt; } http://codesays.com/2014/solution-to-count-distinct-slices-by-codility/ |
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
|
def solution(M, A):
accessed = [-1] * (M + 1) # -1: not accessed before
# Non-negative: the previous occurrence position
front, back = 0, 0
result = 0
for front in xrange(len(A)):
if accessed[A[front]] == -1:
# Met with a new unique item
accessed[A[front]] = front
else:
# Met with a duplicate item
# Compute the number of distinct slices between newBack-1 and back
# position.
newBack = accessed[A[front]] + 1
result += (newBack - back) * (front - back + front - newBack + 1) / 2
if result >= 1000000000: return 1000000000
# Restore and set the accessed array
for index in xrange(back, newBack):
accessed[A[index]] = -1
accessed[A[front]] = front
back = newBack
# Process the last slices
result += (front - back + 1) * (front - back + 2) / 2
return min(result, 1000000000)
|
