11

I am trying to solve the codility MissingInteger problem link:

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.

My solution is:

class Solution {
    TreeMap<Integer,Object> all = new TreeMap<Integer,Object>();

    public int solution(int[] A) {

        for(int i=0; i<A.length; i++)
            all.put(i+1,new Object());

        for(int i=0; i<A.length; i++)
            if(all.containsKey(A[i]))
                all.remove(A[i]);

        Iterator notOccur = all.keySet().iterator();
        if(notOccur.hasNext())
            return (int)notOccur.next();

        return 1;

    }
}

The test result is:

enter image description here

Can anyone explain me why I got this two wrong answers? Especially the first one, if there is only one element in the array, shouldn't the only right answer be 1?

4
  • Someone is running through this entire thread and down-voting old answers. Why? Jul 2, 2018 at 4:10
  • @QuestMonger: it is not possible to say unless the voter wishes to let you know. Don't worry about it. My guess is that a large number of answers have recently come in, and they are not all of good quality. I wonder if someone is promoting this question externally, and it is getting a blizzard of attention (with the result that some answers are not even answering the question posed).
    – halfer
    Jul 2, 2018 at 21:49
  • Ah, this question is the subject of a Meta question.
    – halfer
    Jul 2, 2018 at 21:58
  • 2
    @QuestMonger The issue is that there are only 2 answers here (the accepted one, and another) which actually attempt to solve the problem asked in the question (why OP's code fails those 2 tests). All of the other answers are off-topic, and if this question asked the question which they are answering (how to solve the referenced Codility problem), then it would be closed for being too broad for StackOverflow.
    – Radiodef
    Jul 2, 2018 at 22:03

5 Answers 5

35

Here is my answer, got 100/100.

import java.util.HashSet;

class Solution {
    public int solution(int[] A) {
        int num = 1;
        HashSet<Integer> hset = new HashSet<Integer>();

        for (int i = 0 ; i < A.length; i++) {
            hset.add(A[i]);                     
        }

         while (hset.contains(num)) {
                num++;
            }

        return num;
    }
}
6
  • 4
    The while loop should be moved out of the for loop since it just needs to run at the end instead on every iteration of the for loop.
    – Benjamin
    Oct 8, 2017 at 14:39
  • 1
    Add only positive number in HashSet will work fine: for (int n : A) { if (n > 0) set.add(n); } May 18, 2018 at 4:49
  • 5
    This does not answer Ops question! It merely answers the code challenge.
    – Ryan Leach
    Jun 8, 2018 at 2:57
  • 2
    It was getting tedious, and to do so for all the answers that don't answer the OP's actual question would require more flags then I currently have. 90% of the answers here are trainwrecks, just posting answers for the coding challenge without helping OP at all.
    – Ryan Leach
    Jun 8, 2018 at 4:25
  • 2
    @Cœur You can find a meta question that I posted in response to your comment: meta.stackoverflow.com/questions/369183/…
    – Ryan Leach
    Jun 8, 2018 at 4:37
16

returns the minimal positive integer that does not occur in A.

So in an array with only one element, if that number is 1, you should return 2. If not, you should return 1.

I think you're probably misunderstanding the requirements a little. Your code is creating keys in a map based on the indexes of the given array, and then removing keys based on the values it finds there. This problem shouldn't have anything to do with the array's indexes: it should simply return the lowest possible positive integer that isn't a value in the given array.

So, for example, if you iterate from 1 to Integer.MAX_VALUE, inclusive, and return the first value that isn't in the given array, that would produce the correct answers. You'll need to figure out what data structures to use, to ensure that your solution scales at O(n).

2
  • 3
    My understanding is, if the array is [1], there's no missing element, if the array is [2] or some other number, the missing one is always 1, where did I understand wrong?
    – Tom
    Oct 23, 2014 at 16:03
  • 3
    @Tom you're not looking for a missing element. You're looking for the smallest possible integer which isn't in the array. Hence given the array [1] the answer is 2
    – extols
    Oct 23, 2014 at 16:07
4

I have done the answer inspired by the answer of Denes but a simpler one.

int counter[] = new int[A.length];

// Count the items, only the positive numbers
for (int i = 0; i < A.length; i++)
    if (A[i] > 0 && A[i] <= A.length)
        counter[A[i] - 1]++;

// Return the first number that has count 0
for (int i = 0; i < counter.length; i++)
    if (counter[i] == 0)
        return i + 1;

// If no number has count 0, then that means all number in the sequence
// appears so the next number not appearing is in next number after the
// sequence.
return A.length + 1;
2
  • 1
    They said max space complexity is O(n) but you need more than this for your counter since the integer range is -1000000 to 1000000 but the max N is 100k
    – Markus
    May 7, 2018 at 16:48
  • 5
    This does not answer Ops question! It merely answers the code challenge.
    – Ryan Leach
    Jun 8, 2018 at 2:57
1

returns the minimal positive integer that does not occur in A

The key here is that zero is not included in the above (as it is not positive integer). So the function should never return 0. I believe this covers both of your failed cases above.

edit: due to the fact that question has been changed since this was written this answer isn't really relevant anymore

5
  • Hi, it never returns 0.
    – Tom
    Oct 23, 2014 at 15:54
  • 1
    @Tom: According to your screenshot, it did, in both the failed cases. Oct 23, 2014 at 15:55
  • "got 0 expected 2" and "got 0 expected 100001". That says your function returned 0 in both instances.
    – extols
    Oct 23, 2014 at 15:56
  • 1
    all.put(i+1,new Object());, the map doesn't contain 0, how can a 0 be returned?
    – Tom
    Oct 23, 2014 at 15:57
  • Hi, sorry, my bad, could you check the updated question?
    – Tom
    Oct 23, 2014 at 15:59
1

Very little wrong. Just the last line

return 1;

should read

return A.length + 1;

because at this point you've found & removed ALL KEYS from 1 to A.length since you have array entries matching each of them. The test demands that in this situation you must return the next integer above the greatest value found in array A. All other eventualities (e.g. negative entries, missing 1, missing number between 1 and A.length) are covered by returning the first unremoved key found under iteration. Iteration here is done by "natural ordering", i.e. 1 .. max, by default for a TreeMap. The first unremoved key will therefore be the smallest missing integer.

This change should make the 2 incorrect tests okay again. So 50/50 for correctness.

Efficiency, of course, is another matter and one that carries another 50 points. Your use of the TreeMap data structure here brings a time penalty when evaluating the test results. Simpler data structures (that essentially use your algorithm) would be faster.

This more primitive algorithm avoids sorting and copies all entries > 1 onto a new array of length 100001 so that index x holds value x. It actually runs faster than Serdar's code with medium and large input arrays.

public int solution(int[] A) 
{
    int i = 0,
        count = 0,
        N = A.length;
    int[] B = new int[100001];      // Initially all entries are zero

    for (i = 0; i < N; i++)         // Copy all entries > 0 into array B ...
    {
        if (A[i] > 0 && A[i] < 100001)
        {
            B[A[i]] = A[i];         // ... putting value x at index x in B ...
            count++;                // ... and keep a count of positives
        }
    }

    for (i = 1; i < count + 1; i++) // Find first empty element in B 
    {
        if (B[i] == 0)  
        {            
            return i;               // Index of empty element = missing int 
        }
    }
                                    // No unfilled B elements above index 0 ? 
    return count + 1;               // => return int above highest filled element
}
0

Not the answer you're looking for? Browse other questions tagged or ask your own question.