PHP code to find first covering prefix of an array

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 \leq P < N$ and such that every value that occurs in array A also occurs in sequence $A[0], A[1], \ldots, A[P]$.

For example, the first covering prefix of array A such that

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

is 3, because sequence A[0], A[开发者_如何学Go1], A[2], A[3] equal to 2, 2, 1, 0 contains all values that occur in array A.

Write a function

int ps(int[] A);

that given a zero-indexed non-empty array A consisting of N integers returns the first covering prefix of A. Assume that $N <= 1,000,000$. Assume that each element in the array is an integer in range [0..N-1].

For example, given array A such that A[0]=2 A[1]=2 A[2]=1 A[3]=0 A[4]=1

the function should return 3, as explained in the example above.

This is a very short solution. Pretty but won't scale well.

function ps($A) {

    $cp = 0; // covering prefix

    $unique = array_unique($A); // will preserve indexes

    end($unique); // go to end of the array

    $cp = key($unique); // get the key

    return $cp;

}

Here's a simple way :

function covering_prefix ( $A ) {
    $in=array();
    $li=0;

    $c=count($A);
    for($i=0 ;$i<$c ; $i++){
        if (!isset($in[$A[$i]])){
           $in[$A[$i]]='1';
           $li=$i;
        }
    }
    return $li;
}

Here is a solution using ruby

def first_covering_prefix(a)
    all_values = a.uniq
    i = 0
    a.each do |e|
        all_values.delete(e)
        if all_values.empty?
            return i
        end
        i = i + 1
    end
end

it's a 83% answer, because of use of in_array, a better solution already proposed by ronan

function solution($A) {
    // write your code in PHP5
    $in=array();
    $li=0;
    for ($i=0; $i < count($A); $i++) { 
        # code...
        if (!in_array($A[$i], $in)){

            $in[]=$A[$i];
            $li=$i;

        }

    }
    return $li;
}