Return to Answer

##Review

Review

I think that the best option would be to sort the array, am I right?

Not exactly. You could sort it and reduce the complexity using a binary search to O(n log(n)). But you could much better by copying the array into a HashMap and getting O(n) assuming no perverted distribution (the worst case hash table access is O(n), but occurs very rarely).

The search itself could be even faster, when using two sorted arrays. As all the data come from a Set, there are duplicates. So whenever the element of the first array at a given position equals to the element of the other array at the same position, you know that you're before the removed element. Using a binary search you can get a complexity of O(log(n)). However, producing the the second array costs O(n), so you don't gain anything w.r.t. the O-notation.

I think that the best option would be to sort the array, am I right?

Not exactly. You could sort it and reduce the complexity using a binary search to O(n log(n)). But you could much better by copying the array into a HashSet and getting O(n) assuming no perverted distribution (the worst case hash table access is O(n), but occurs very rarely).

The search itself could be even faster, when using two sorted arrays. As all the data come from a Set, there are duplicates. So whenever the element of the first array at a given position equals to the element of the other array at the same position, you know that you're before the removed element. Using a binary search you can get a complexity of O(log(n)). However, producing the the second array costs O(n), so you don't gain anything w.r.t. the O-notation.

##Review

private static final Set<Integer> SET = Sets.newTreeSet(Arrays.asList(1, 3, 5, 7));

This is fine for the test data, but then you should define another constant for unsorted, too.

private static int checkElementRemoved(final int[] unsorted) {
 Integer elementRemoved = null;
 for (Integer number : SET) {
 if (!arrayContains(unsorted, number)) {
 // O(n^2) complexity
 elementRemoved = number;
 break;
 }
 }
 return elementRemoved;
}

You're not checking anything. Call it find... or alike. Don't use useless variables. It all can be reduced to

private static int checkElementRemoved(int[] unsorted, Iterable<Integer> set) {
 for (Integer number : set) {
 if (!arrayContains(unsorted, number)) {
 // O(n^2) complexity
 return number;
 }
 }
 throw new WhateverException();
}

Your code secretly throws a NullPointerException when unboxing elementRemoved. This is pretty bad. Throwing NPE explicitly would be much better, but NPE is not the right exception here. Letting your method return an Integer would be better, but only postpone the problem. Actually, IllegalArgumentException sounds right, as it's not allowed to pass an array missing no element.

In any case, you should pass SET as an argument, so that your method is more usable.

private static boolean arrayContains(final int[] unsorted, final int number) ...

This is no better than Arrays.asList(unsorted).contains(number). But as already said, create a HashSet and use it for speed.