Codility - MissingInteger  

by ne on 2022-02-16 under Algo/DS/Problems tagged with codility

Hi,
The problem description is in the comments above the solution below.

The problem belongs to Codility, you can try out it yourself on their platform.


/**
 * Write a function:
 * class Solution { public int solution(int[] A); }
 * that, given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A.
 * For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5.
 * Given A = [1, 2, 3], the function should return 4.
 * Given A = [−1, −3], the function should return 1.
 */
public class MissingInteger {

    public int solution(int[] A) {
        // write your code in Java SE 8
        int[] p = new int[A.length + 2];
        for (int i = 1; i < p.length; i++) {
            p[i] = 1;
        }
        for (int i = 0; i < A.length; i++) {
            if (A[i] >= 0 && A[i] < p.length)
                p[A[i]]--;
        }
        int tor = 0;
        for (int i = 1; i < p.length; i++) {
            if (p[i] == 1 && p[i] > tor) {
                tor = i;
            }
        }
        return tor;
    }
}