Finding the missing integer (Codility tests)

Question

I'm facing a really strange issue with this exercise found on Codility, here's the task description:

Write a function:

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

that, given a non-empty zero-indexed array A of N integers, returns the minimal positive integer that does not occur in A.

For example, given:

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

the function should return 5.

Assume that:
N is an integer within the range [1..100,000];
each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.

And there's my code:

class Solution {
    public int solution(int[] A) {
        SortedSet set = new TreeSet();
        for (int i = 0; i < A.length; i++)
            if (A[i] > 0)
                set.add(A[i]);
        Iterator it = set.iterator();
        int previous = 0, element = 0;
        try { previous = (int)it.next(); }
        catch (NoSuchElementException e) { return 1; }
        while (it.hasNext()) {
            element = (int)it.next();
            if (element!=(previous+1)) break;
            previous=element;
        }
        if (previous+1 < 1) return 1;
        return previous+1;
    }
}

Code analysis:

http://i.stack.imgur.com/IlMxP.png

I'm trying to figure out why does my code provide the wrong output only on that test, is someone able to help me?

Thanks in advance!

Answer 1

My solution that scored 100/100

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.util.Arrays;

class Solution {

    public int solution(int[] A) {

        int smallest = 1;

        Arrays.sort(A);
        for (int i = 0; i < A.length; i++) {

            if (A[i] == smallest) {

                smallest++;
            }
        }

        return smallest;
    }
}

Worse time was on 'large_2' test case and it was 0.292s.

I'd say pretty good.

If you need explaining buzz me so I can expand the answer :)

Cheers.

Answer 2

I've found a solution that scores 100/100 using binarySearch.

Here is the code:

import java.util.*;

class Solution {
    public int solution(int[] A) {
        Arrays.sort(A);
        int i = 1;
        while (i <= A.length) {
            int res = Arrays.binarySearch(A, i); 
            if (res < 0) {
                return i;
            }
            i++;
        }
        return i;
    }
}

Answer 3

Another answer with O(n) complexity:

 int solution(int A[]) {
    int smallestPostive=0;
    int maxPositive = 0;
    for (int number: A) { //Find maximum positive
        if (number> maxPositive) {
            maxPositive = number;
        }
    }
    if (maxPositive == 0) { // if all numbers are negative, just return 1
        return smallestPostive+1;
    }
    int[] data = new int[maxPositive]; //new array with all elements up to max number as indexes
    for (int element: A) {  // when you encounter a +ve number, mark it in the array
        if (element> 0)
            data[element-1] = 1;
    }
    for (int count=0; count<maxPositive;count++) {
        if (data[count] == 0) {  // find the unmarked smallest element
            smallestPostive = count+1;
            break;
        }
    }
return smallestPostive==0?maxPositive+1:smallestPostive; //if nothing is marked return max positive +1
}

Answer 4

Hash table solution

Here's my 100% solution that uses a hash table. It's written in JS, but the context is similar in other languages.

function solution(A) {

    let hashTable = {}, min = 0;
    
    // build the hash table
    for (const num of A) hashTable[num] = 1;

    // return the first available integer
    while(1) if (!hashTable[++min]) return min;
}

Answer 5

Since we know the absolute minimum can only be 1, we can start there.

   import java.util.Arrays;
    class Solution {
        public int solution(int[] A) {
            Arrays.sort(A);     
            int min = 1; 

            for (int i = 0; i < A.length; i++){
                if(A[i]== min){
                    min++;
                }
            }   
            //min = ( min <= 0 ) ? 1:min;
            return min;    
        }
    }

Answer 6

I did something similar by adding all data to a hashSet and using the array index to check the hashset. There's a few edge cases too. You can also achieve the same results by adding to a hashmap and using the array indexes to look for the the day in order since the keyset is a set.

https://app.codility.com/demo/results/trainingVHZNXJ-68S/

 public int solution(int[] A) {
    Set<Integer> set = new HashSet<Integer>();
    for (int i = 0; i < A.length; i++) {
      set.add(A[i]);
    }

    int max = 0, missing = -1;
    for (int i = 1; i <= A.length; i++) {
      max = i;
      if (!set.contains(i)) {
        missing = i;
        break;
      }
    }
    return missing == -1 ? max + 1 : missing;
  }

Answer 7

    import java.util.*;
    
    class Solution {
    
        public int solution(int[] A) {
            // write your code in Java SE 8
            Arrays.sort( A );
    
            //Print array to confirm
            int smallestVal = 1;
            int len = A.length;
            int prev=0;
    
            for(int i=0; i<len; i++){
                // Filtering all values less than 1 AND filtering the duplicates
                if( A[i] >= 1 && prev != A[i]){
                    if(smallestVal == A[i]){
                        smallestVal++;
                    }else{
                        return smallestVal;
                    }
                    prev = A[i];
                }
            }
            return smallestVal;
        }
    
        public static void main(String[] args) {
            Solution sol = new Solution();
            sol.testOutput(new int[]{-9, 1, 2},3);
            sol.testOutput(new int[]{-9, 2},1);
            sol.testOutput(new int[]{92,93,0,-100},1);
            sol.testOutput(new int[]{-1000000},1);
            sol.testOutput(new int[]{-5,6,-3,7,3,10,1000,-4000},1);
            sol.testOutput(new int[]{999999,-1000000,999998,-999999,-999998,1000000},1);
            sol.testOutput(new int[]{4,6,1,0,-9,10,0,-4},2);
            sol.testOutput(new int[]{-1},1);
            sol.testOutput(new int[]{1},2);
            sol.testOutput(new int[]{1000},1);
            sol.testOutput(new int[]{9,10, 12,1000000},1);
            sol.testOutput(new int[]{1, 3, 6, 4, 1, 2},5);
            sol.testOutput(new int[]{0, 2, 3},1);
            sol.testOutput(new int[]{-1,-3,-10,-100},1);
            sol.testOutput(new int[]{100, 98, 93,78,84, 34,0,1,2,102,130,123,150,200,199,185,149},3);
            sol.testOutput(new int[]{10,9,8,8,7,6,5,4,3,2,1,0,20,19,18,17,16,15,14,13,12},11);
        }
    
        private void testOutput(int[] in, int exp){
            Solution sol = new Solution();
            if(sol.solution(in) == exp){
                System.out.println("PASS");
            }else{
                System.out.println("Expected/Got:"+exp+" / " + sol.solution(in));
            }
        }
    }

Answer 8

Here my 100% O(N) complexity solution with Python.

def solution(A):
    smallest = 1
    B = {a for a in A}

    while(smallest in B):
        smallest += 1

    return smallest