10
\$\begingroup\$

I have to write the following method:

I have sorted array of integers and in this array every integer repeats twice, except two elements. I have to find these two elements.

  • Input: 1, 1, 2, 3, 3, 4, 4, 5
  • Output: 2, 5

This is my solution:

private static int[] findUniques(int[] arr) {
    int[] res = new int[2];
    int start = 0;    // start can be 0 or 1 only; it indicates the position in array res
    for (int i = 0; i < arr.length-2; ) {
        if(arr[i] == arr[i+1]){
            i+=2;
            if(i == arr.length-1){
                res[1] = arr[arr.length-1];
            }
        }
        else{
            if(arr[i+1] == arr[i+2]){
                res[start] = arr[i];
                start++;
                i+=3;
                if(i == arr.length-1){
                    res[1] = arr[arr.length-1];
                }
            }
            else{
                res[start] = arr[i];
                res[start+1] = arr[i+1];
                break;
            }
        }
    }
    return res;
}

Is there a clearer way to find these two values? I don't like that I have so many if-else statements, but I don't know how to write it better.

\$\endgroup\$
4
  • \$\begingroup\$ Are there any restrictions to the code? \$\endgroup\$
    – skiwi
    Jul 7, 2014 at 14:26
  • \$\begingroup\$ @JerryCoffin yes, I agree, but since the given array is sorted there is no difference in comparing with XOR or with == \$\endgroup\$ Jul 7, 2014 at 14:33
  • \$\begingroup\$ @skiwi no, what restrictions? Just given sorted array, find the two non-repeating values as fast as possible. My code works but Im looking for more clear way to perform the search. \$\endgroup\$ Jul 7, 2014 at 14:36
  • \$\begingroup\$ With restrictions I meant the ability to use Java library classes. Also, what is as fast as possible, do you need to have some kind of asymptotic performance? \$\endgroup\$
    – skiwi
    Jul 7, 2014 at 14:51

3 Answers 3

8
\$\begingroup\$

For each number in the list, either

  • there is no next (at end of src list) - add to result list
  • the next is different - add to the result list, increment result count (if all answers found, return)
  • the next is the same; skip next, (add 2 to src pointer)
public int[] findUnique(int[] src){
    int[] res =  new int[2];
    int resIdx = 0;

    for(int i = 0; i < src.length;){
        // at the end of the list, or next is different
        if(i == src.length-1 || src[i] != src[i+1]){
            res[resIdx++] = src[i++];
            if (resIdx== 2) break;
        } else{
            // not different; skip next item
            i+=2;
        }
    }
    return res;
}
\$\endgroup\$
2
  • \$\begingroup\$ if (++i == 2) break;? I believe that part is not correct. (Easy to fix though) \$\endgroup\$ Jul 7, 2014 at 15:06
  • \$\begingroup\$ Yep. Should be resIndex. With i++ in previous line. Hopefully. Trying to update using phone on bus :? \$\endgroup\$
    – AlanT
    Jul 7, 2014 at 15:43
8
\$\begingroup\$

Naming, naming, naming.

OK, naming things totally correct is one of the hardest things in programming. But then there's also... bad naming.

Instead of naming a variable something and explaining it with a comment like this:

int start = 0;    // start can be 0 or 1 only; it indicates the position in array res

Use the information that you write in the comment to name it correctly.

Let's look at your comment:

(variable) can be 0 or 1 only; it indicates the position in array res

Now here's the important parts of this comment in bold:

(variable) can be 0 or 1 only; it indicates the position in array res

So let's make permutations and variations of this: arrayResultPosition, resultArrayPosition, positionArrayResult, positionResultArray, indexResult, resultIndex... Pick one. You want something that's not too long, but it should be long enough to be self-documenting. My personal favorite here is resultIndex.


Scottish Notation

There's a thing called Hungarian Notation where you prefix a variable name with the type of the variable, such as aNumbers (array named 'numbers'), sName (string for 'name'), but your variable name int[] arr is something I'm calling Scottish Notation. Scottish Notation is, in my opinion, even worse than Hungarian Notation.

You're using a very very short name (Scots are said to be cheap so they don't want to waste letters). And yet you haven't provided any information whatsoever about what this variable is used for. You have only stated the obvious, arr as short for array. I can see that it's an array from the use of [].

A better name would be input or possibly inputNumbers (although naming it numbers is a bit overkill as it is an int[] after all, of course it contains numbers! As stated before, naming things totally correct is hard...)

Please avoid Scottish Notation!

\$\endgroup\$
2
  • \$\begingroup\$ If you're talking about cheapskates, you could also call it swabian notation... I guess I'll go with that </selfirony> \$\endgroup\$
    – Vogel612
    Jul 7, 2014 at 19:27
  • 5
    \$\begingroup\$ And we have the Canadian Notation where you suffix all your variables with eh! \$\endgroup\$
    – Marc-Andre
    Jul 7, 2014 at 19:39
1
\$\begingroup\$

For performance you can perform a binary search over the array since a perfect array should contain each number twice, at every position a[i] == i/2+1. So for an array length n start with i = n/2-1; And check: array[i] == i/2+1 and array[i+1] == i/2+1

If they are both true you know both single values appear after a[i], so in the range a[i+2]-a[n-1], if only one holds true, there is one target in the lower half and one in the higher half, if both are false, both targets must be in the lower half.

But this is just general performance and algorithm recommendation, for cleaner code and review I recommend you to the other answers!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ As I understood it, the only guarantee is that the array is sorted, it could contain 1 1 4 7 7 12 12 42 which would break this approach. \$\endgroup\$ Jul 7, 2014 at 15:29
  • \$\begingroup\$ What a shame... but we could still use this information and binary-search for the point where the count is off by one - then we had a point in between both elements. But if they are right next to each-other we ould also be in O(n) but with more overhead. But in other cases much faster! \$\endgroup\$
    – Falco
    Jul 7, 2014 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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