- Back to Home »
- code , coding problem , java , programming »
- Coding Problem - alpha2010

Saturday, 10 August 2013

**Problem**

A non-empty zero-indexed 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] = 1
```

is 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

that, given a zero-indexed non-empty array A consisting of N integers, returns the first covering prefix of A.int solution(int A[], int N);

Assume that:

For example, given array A such that

- 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].

```
``````
A[0] = 2 A[1] = 2 A[2] = 1
A[3] = 0 A[4] = 1
```

the function should return 3, as explained above.Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

**Solution**

Java - Download Solution.java

/*Solution.java

* This program is free software: you can redistribute it and/or modify

* it under the terms of the GNU General Public License as published by

* the Free Software Foundation, either version 3 of the License, or

* (at your option) any later version.

*

* This program is distributed in the hope that it will be useful,

* but WITHOUT ANY WARRANTY; without even the implied warranty of

* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

* GNU General Public License for more details.

*

* Copyright 2013 Maven Scientists http://mavenscientists.com

*/

package alpha2010;

import java.util.HashSet;

import java.util.Set;

/**

*

* @author Maven Scientists (http://blog.mavenscientists.com)

* @time Aug 10, 2013 8:47:07 PM

*/

public class Solution {

int solution(int[] A, int N)

{

int result = 0;

Set<Integer> set = new HashSet<>();

for(int I = 0; I <N; I++ )

{

if(set.add(A[I]))

result = I;

}

return result;

}

public static void main(String[] args)

{

int[] A = {2,2,1,0,1};

int result;

Solution sol = new Solution();

result = sol.solution(A, A.length);

System.out.println(result);

}

}