Codility: Missing Integer - Java SE 8

Question

that, given a non-empty zero-indexed array A of N integers, returns the minimal positive integer (greater than 0) that does not occur in A. For example, given:

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

the function should return 4. Assume that:

in other words, A[K] = 2 for each K (0 <= K <= 50000), the given implementation works too slow, but the function would return 50,000

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1...100,000]
each element of array A is an integer the range [1..N]

My Answer is not yet successful! What is wrong with it? First let me state the obvious errors

return value - I return 4 in the first result and that was successful but the second return is 1 that is not correct for the reason that the expected result is 50,000

my code, which works but the only first result is correct and second is not.

import java.util.*;
class Solution {
        int solution(int[] A) {
        int[] AN = Arrays.stream(A).filter(n -> n > 0).distinct().sorted().toArray();
        int N = AN.length;
        int min = 1;
        int i = 0;
        while (i < N) {
            min = i+1;
            if (min == N) {
                min = Math.max(min , Math.abs(i-N));
            }
            i++;
        }
        return min;
    }
}

user_12436427 · Answer

Note: In the example you gave, the missing integer is 3 and not 4

The performance issue is probably caused by using the distinct and sorted.

I'll create an algorithm based on the sorted array, so its complexity is O(n log n).

First we sort the array:

Arrays.sort(A);

Next we skip negative or zero numbers

while (i < A.length && A[i] <= 0)
   i++;

If now the array is fully parsed or the current element A[i] is not 1, then the solution is 1.

If it's not the case, we continue parsing the array A, we initiliase missing variable to 1 and if the current element equals the missing element we increment i, or if the current element is equal missing + 1 we increment missing otherwise we stop, we found our missing integer.

In the end if our array is fully parsed without any mismatch between missing variable and A[i] then we increment missing.

The full code:

Arrays.sort(A);

int missing = 1;
int i = 0;
        
while (i < A.length && A[i] <= 0)
   i++;

if (i < A.length && A[i] == 1) {
   while (i < A.length) {
       if (A[i] == missing) {
           i++;
       } else if (A[i] == missing + 1) {
           missing++;
       } else {
           missing++;
           break;
       }
   }
            
   missing = i >= A.length ? missing + 1 : missing;
}

System.out.println(missing);

Codility: Missing Integer - Java SE 8

1 Answers