A non-empty array A consisting of N integers is given. The first covering prefix of array A is the smallest integer P such that 0≤P<N and such that every value that occurs in array A also occurs in sequence A[0], A[1], ..., A[P].
For example, the first covering prefix of the following 5−element array A:
A[0] = 2 A[1] = 2 A[2] = 1 A[3] = 0 A[4] = 1is 3, because sequence [ A[0], A[1], A[2], A[3] ] equal to [2, 2, 1, 0], contains all values that occur in array A.
Write a function
int solution(int A[], int N);
that, given a non-empty array A consisting of N integers, returns the first covering prefix of A.
For example, given array A such that
A[0] = 2 A[1] = 2 A[2] = 1 A[3] = 0 A[4] = 1the function should return 3, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..1,000,000];
- each element of array A is an integer within the range [0..N-1].
Segmentation Fault
Segmentation Fault
?????
?????
func.c: In function 'solution': func.c:14:1: error: expected declaration or statement at end of input } ^ func.c:14:1: warning: control reaches end of non-void function [-Wreturn-type] } ^
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
//e
int i, pivot;
for (pivot=N-1;pivot>=0;pivot--){
for (i=pivot;i>=0;i--){
if (A[i]==A[pivot]) break;
}
if (i==-1 && A[i] != A[pivot])
return pivot;
}
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
//e
int i, pivot;
for (pivot=N-1;pivot>=0;pivot--){
for (i=pivot-1;i>=0;i--){
if (A[i]==A[pivot]) break;
}
if (i==-1 && A[i] != A[pivot])
return pivot;
}
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
//e
long i, pivot;
for (pivot=N-1;pivot>=0;pivot--){
i=pivot-1;
while (A[i]!=A[pivot] && i>0){
i--;
}
if (i==0 && A[i] != A[pivot])
return pivot;
}
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
//e
long i, pivot;
for (pivot=N-1;pivot>=0;pivot--){
i=pivot-1;
while (A[i]!=A[pivot] && i>0){
i--;
}
if (i==0 && A[i] != A[pivot])
return pivot;
}
}
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
int solution(int A[], int N) {
//e
long i, pivot;
for (pivot=N-1;pivot>=0;pivot--){
i=pivot-1;
while (A[i]!=A[pivot] && i>0){
i--;
}
if (i==0 && A[i] != A[pivot])
return pivot;
}
}
The following issues have been detected: timeout errors.
random test 100 000 elements and n/log_2 n values.
running time: 0.15 sec., time limit: 0.10 sec.