Searching a value using for-loop and

Question

The question is this:

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Input: [4,1,2,1,2]
Output: 4

my code is:

public static int singleNumber(int[] nums) {
     int answer = 0;
        for (int i =0; i<nums.length-1; i++) {
            for(int j = i+1; j<nums.length; j++) {
                if(nums[i] != nums[j]) {
                 answer = nums[i];      //this should be where I am wrong.
                }
            }
        }
        return answer;
    }

I know that the output was 4 and then now it will be changed to 1. I'm trying to figure out how not to change the found value once found.

Answer 1

The logic is wrong - your inner loop finds every number that isn't the only number in the array.

I'd maintain a Set to track the numbers I've encountered. The first time you encounter a number, you add it to the Set. The second time you encounter it, you remove it from the Set. Once you're done going over the array, you'd have a Set with a single element, which is your answer:

public static int singleNumber(int[] nums) {
    Set<Integer> unique = new HashSet<>();
    for (int num : nums) {
        // add returns true if num is indeed new to unique
        if (!unique.add(num)) {
            unique.remove(num);
        }
    }

    return unique.iterator().next();
}