Single Number

• 1. Iterate through the array with an outer loop from i = 0 to n-1.
• 2. For each element nums[i], initialize a count variable to 0.
• 3. Start an inner loop from j = 0 to n-1.
• 4. Inside the inner loop, if nums[i] is equal to nums[j], increment count.
• 5. After the inner loop finishes, check if count is equal to 1.
• 6. If count is 1, nums[i] is the single number. Return nums[i].

The brute force method is the most straightforward way to solve the problem, but also the least efficient. The core idea is to check every element and see how many times it appears in the array.

We use two nested loops. The outer loop picks an element, and the inner loop iterates through the entire array to count the occurrences of the picked element. If the count for an element is exactly one, we have found our single number and can return it immediately.

1public int singleNumber(int[] nums) {2    for (int i = 0; i < nums.length; i++) {3        int count = 0;4        for (int j = 0; j < nums.length; j++) {5            if (nums[i] == nums[j]) {6                count++;7            }8        }9        if (count == 1) {10            return nums[i];11        }12    }13    return -1; // Should not be reached given the problem constraints14}

• 1. Sort the input array nums in ascending order.
• 2. Iterate through the sorted array with a step of 2 (i.e., i = 0, 2, 4, ...).
• 3. In each iteration, compare nums[i] with the next element nums[i+1].
• 4. If nums[i] is not equal to nums[i+1], it means nums[i] is the unique element. Return nums[i].
• 5. If the loop finishes without returning, it implies the single element is the last element in the array. Return nums[nums.length - 1].

By sorting the array, we can group identical elements together. For example, [4,1,2,1,2] becomes [1,1,2,2,4] after sorting.

After sorting, we can iterate through the array, checking elements in pairs. If nums[i] is not equal to nums[i+1], then nums[i] must be the single element because its pair would have been at nums[i+1]. We must be careful with the boundary conditions, especially the last element, which could be the single number if all preceding elements form pairs.

1import java.util.Arrays;2 3public int singleNumber(int[] nums) {4    Arrays.sort(nums);5    for (int i = 0; i < nums.length - 1; i += 2) {6        if (nums[i] != nums[i+1]) {7            return nums[i];8        }9    }10    // If the loop completes, the single element is the last one11    return nums[nums.length - 1];12}

• 1. Initialize an empty hash set.
• 2. Iterate through each number num in the input array nums.
• 3. Check if num is present in the hash set.
• 4. If it is present, remove num from the set.
• 5. If it is not present, add num to the set.
• 6. After the loop, the hash set will contain exactly one element.
• 7. Return this single element.

A hash set provides average O(1) time complexity for add, remove, and contains operations. We can leverage this to solve the problem in linear time.

We iterate through the input array. For each number, we try to add it to the set. If the number is already in the set (which add method can tell us by returning false), it means we have seen it once before, so this is its second appearance. In this case, we remove it from the set. If the number is not in the set, we add it.

After iterating through all the numbers, the hash set will contain only one element: the number that appeared an odd number of times (once, in this case).

1import java.util.HashSet;2import java.util.Set;3 4public int singleNumber(int[] nums) {5    Set<Integer> set = new HashSet<>();6    for (int num : nums) {7        if (!set.add(num)) {8            // If add returns false, it means the element was already in the set9            set.remove(num);10        }11    }12    // The set will have only one element, which is the single number13    return set.iterator().next();14}

• 1. Initialize an integer variable result to 0.
• 2. Iterate through each number num in the input array nums.
• 3. In each iteration, update result by performing a bitwise XOR with the current number: result = result ^ num.
• 4. After the loop completes, the value of result will be the single number that appears only once.
• 5. Return result.

The XOR operation has two key properties that are useful here:

• A number XORed with itself results in 0 (e.g., x ^ x = 0).
• A number XORed with 0 results in the number itself (e.g., x ^ 0 = x).
• XOR is commutative and associative, meaning the order of operations doesn't matter.

We can initialize a variable, say a, to 0. Then, we iterate through the array and XOR each element with a. For any number that appears twice, say x, it will be XORed into the accumulator twice: (... ^ x ... ^ x ...). Due to the properties of XOR, this is equivalent to (... ^ (x ^ x) ...) which is (... ^ 0 ...). So, all the paired numbers will effectively cancel each other out.

The single number, say y, appears only once. It will be XORed into the accumulator once. The final result will be 0 ^ y, which is y.

For example, with nums = [4,1,2,1,2], the calculation would be 0 ^ 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4.

1public int singleNumber(int[] nums) {2    int result = 0;3    for (int num : nums) {4        result ^= num;5    }6    return result;7}