Display minimum value that is not in array

[John_165]

Question from codility test

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.

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 within the range [−1,000,000..1,000,000].

This is what I have tried

class Solution {
    public int solution(int[] A) {

        int minValue = A[0];

        do {
            for (int i = 0; i < A.length; i++) {
                if (A[i] < minValue) {
                    minValue = A[i];
                }
            }
        } while (contains(A, ++minValue) == true);

        return minValue;
    }

    public static boolean contains(int[] arr, int item) {
        for (int n : arr) {
            if (item == n) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int[] intArray = new int[]{1, 3, 6, 4, 1, 2};
        int ans = s.solution(intArray);
        System.out.println(ans);
    }
}

I get infinity loop, no result displayed.
Can someone please point me out what is wrong here ?

[JamesCherrill]

Your do/while will loop forever because the body always sets the same value for minValue and therefore the while clause always returns the same value.
(A couple of quick print statements would have revealed this immediately.)
If its stil not clear, add some prints so you can see what's going on.

[JamesCherrill]

Yes, it does, but then you go back round the loop and lines 7-11 set it back to the lowest value in the array every time

[John_165]

Where should I put the do/while loop ?

[JamesCherrill]

To be honest I don't understand what you intended with that loop anyway.
All you need to make it work is

    int solution(int[] A) {
        int n = 0;
        while (contains(A, ++n));
        return n;
    }

... but that's the simplest solution, not an efficient one - it's O(N^2) and you can get O(NlogN) by pre-sorting the array, and O(N) by cunning stuff with a second array. ;)

[John_165]

Did the above code will find minimum value in array A ?

[JamesCherrill]

No, it finds the minimum value NOT in the array!

ps: If I was doing that for real I would consider including a set of redundant parentheses for the while loop to make it really clear what was intended, ie

 int solution(int[] A) {
        int n = 0;
        while (contains(A, ++n)){}
        return n;
    }

(although the two versions are exactly equivalent)

[John_165]

Thanks James

class Solution {

    public int solution(int[] A) {

        int n = 0;
        while (contains(A, ++n)) ;
        return n;
    }

    public static boolean contains(int[] arr, int item) {

        for (int n : arr) {
            if (item == n) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int[] intArray = new int[]{5, 3, 2, 10};
        int ans = s.solution(intArray);
        System.out.println(ans);
    }
}

[JamesCherrill]

Thanks for the thanks!

Write an efficient algorithm ...

I posted that code to show what was wrong with your original loop, but that solution is NOT an efficient one. Consider it a starting point maybe, but to meet the requirement you will need to research some of the ways in which this can be made much more efficient for large arrays. It's a stadard question, so you will find lots of discussion aboit it with a simple Google.