An algorithm to find the smallest positive integer that does not occur in a given array.

Following examples.

  • [1, 3, 6, 4, 1, 2, 7] then return 5
  • [-1, 1, 2, 3] the return 4
  • [−1, −3, -10] then return 1
  • [−10000, 3] then return 1

Following the solution

public boolean isAllNegative(int[] Arr){
    return Arr[Arr.length-1] < 0;
}

public boolean isFirtValueBiggerThenOne(int[] Arr){
    return Arr[0] > 1;
}

public boolean isFirtPositiveBiggerThenOne(int[] Arr, int pos){
    return Arr[pos-1] < 0 && Arr[pos] > 1;
}

public int algo(int[] Arr) {
    Arrays.sort(Arr);
    if (isAllNegative(Arr) || isFirtValueBiggerThenOne(Arr)){
        return 1;
    }
    int value = Arr[Arr.length-1] +1; // max possible value
    for (int i=1; i < Arr.length; i++){
        if( isFirtPositiveBiggerThenOne(Arr,i)) {
            return 1;
        }
        int previous = Arr[i-1];
        int current = Arr[i];
        if (previous > 0 && current != previous && current != (previous+1)){
            value = previous+1;
            break;
        }
    }
    return value;
}

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s