0

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 ?

Edited by John_165

2
Contributors
8
Replies
58
Views
2 Weeks
Discussion Span
Last Post by JamesCherrill
0

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.

0

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. ;)

Edited by JamesCherrill: Spelling

0

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)

Edited by JamesCherrill

0

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);
    }
}
1

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.

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.