Find integer that appears exactly once in array of unsorted integers in Java

Question

I have been given an unsorted array of integers where each integer appears precisely twice, excluding one integer which appears only one time. I would like to write a program in Java that finds the integer that appears only once.

Here is my attempt:

int findIntegerThatOccursOnce(int[] arr)
{
    HashSet<Integer> hashSet = new HashSet<Integer>();
    int mSum = 0;
    for(int i = 0; i < arr.length; i++)
    {
        if(hashSet.contains(arr[i]))
        {
          mSum = mSum - arr[i];
        }
        else
        {
          hashSet.add(arr[i]);
          mSum = mSum + arr[i];
        }
    }
    return mSum;
}

My professor said it was a good attempt but there is a better one that uses less space but I cannot see how I can do it with less space? Can anyone help explain about the space issue?

I'm voting to close this question as off-topic because this is working code and asking for a code review. So it belongs on https://codereview.stackexchange.com — , Jun 01 '17 at 02:27
Please read [What types of questions should I avoid asking?](http://stackoverflow.com/help/dont-ask) before attempting to ask more questions. — , Jun 01 '17 at 02:27
@JarrodRoberson I want to know why my solution is bad regarding space I updated my question — Aarron Smith, Jun 01 '17 at 02:37
@JarrodRoberson I don't agree that this is off topic; the OP is asking about a specific problem with the code (it uses too much space), so it's on topic on both sites IMHO — EJoshuaS - Stand with Ukraine, Jun 01 '17 at 03:00

score 1 · Answer 1 · answered Jun 01 '17 at 02:29

Assuming the assertion that all numbers appear twice, except for one value you can xor all of the values and return the result. Like,

static int findIntegerThatOccursOnce(int[] arr) {
    int v = 0;
    for (int i : arr) {
        v ^= i;
    }
    return v;
}

score 0 · Answer 2 · answered Jun 01 '17 at 02:28

Your attempt takes O(n) time and O(n) space and is really quite good as there are a lot of simpler trivial solutions that are “worse” in both time and space.

One possible solution which could take less space could be if you used Exclusive or (XOR) on all the integers in the array; as all the integers that occur twice would cancel.

This would leave you with the one integer that only appears once. This solution would use O(1) space.

Find integer that appears exactly once in array of unsorted integers in Java

2 Answers2