What is the difference between code examples?

Question

I have my code for "Find the missing integer" in Codility

public static int solution(int[] A) {
    ArrayList<Integer> a = new ArrayList<Integer>();
    for(int i=0; i<A.length; i++) if(A[i] >= 0) a.add(A[i]);
    if(a.isEmpty()) {
        return 1;
    }
    a.sort(null);
    if(a.get(0) > 1) {
        return 1;       
    }
    for(int i=0; i<a.size()-1; i++) {
        if(a.get(i) != a.get(i+1) && a.get(i)+1 != a.get(i+1)) {
            return a.get(i)+1;
        }
    }
    return a.get(a.size()-1)+1;
}

This code works for all except Performance tests - large_1.

It gives me an error "got 233 expected 40000".

When i replace this code:

if(a.get(i) != a.get(i+1) && a.get(i)+1 != a.get(i+1)) 
return a.get(i) +1;

with

int a1 = a.get(i);
int a2 = a.get(i+1);
if(a1 != a2 && a1 +1 != a2) return a.get(i) +1;

or

int sub = a.get(i+1) - a.get(i);
if(sub != 0 && sub != 1) return a.get(i) +1;

then there are no errors.(I got 100/100 score when i replace that line)

Is there anyone who can give some explanation for the difference?

They seem the same to me.

Answer 1

if(a.get(i) != a.get(i+1) && a.get(i)+1 != a.get(i+1)) 

Because a is an ArrayList<Integer>, a.get(i) is an Integer, so you're comparing Integers by identity here.

When you added the array elements to the list using a.add(A[i]), they were auto-boxed: the compiler rewrote this to a.add(Integer.valueOf(A[i])).

Only Integers in the range -128..127 are guaranteed to be cached by Integer.valueOf; so if the Integer's value is outside this range, you will be comparing Integers that have equal value but different identities.

On the other hand:

int a1 = a.get(i);    // Unboxing: int a1 = a.get(i).intValue()
int a2 = a.get(i+1);  // Unboxing: int a2 = a.get(i+1).intValue()
if(a1 != a2 && a1 +1 != a2)

a1 and a2 are primitives - you unbox them by assigning them to int variables - so it's fine to compare them by == or !=.

In your first version, replace A != B with !A.equals(B) (or !Objects.equals(A, B)).

Answer 2

Your if condition comparing the Integer objects which obliviously compare the address location of the objects instead of the values. And this is i am sure not expected by you.

Change your if condition to below -

if(a.get(i).intValue() != a.get(i+1).intValue() && a.get(i).intValue()+1 != a.get(i+1).intValue())