Find the Single Unique Element
Given a non-empty array of integers, each integer appears twice except for one. Your task is to find that single, unique integer. This is a common problem that tests your understanding of basic data structures and efficient searching techniques.
Problem Description
You will be provided with an array of integers. In this array, every element appears exactly twice, except for one element which appears only once. You need to write a function that identifies and returns this single, unique element.
Key Requirements:
- The input will always be a non-empty array.
- Every element, except one, will appear exactly twice.
- The function must return the single element that appears only once.
Expected Behavior:
- For an input array
[2, 2, 1], the output should be1. - For an input array
[4, 1, 2, 1, 2], the output should be4.
Edge Cases:
- An array with only one element.
- An array where the unique element is at the beginning or end.
Examples
Example 1:
Input: [2, 2, 1]
Output: 1
Explanation: The number 1 appears only once, while 2 appears twice.
Example 2:
Input: [4, 1, 2, 1, 2]
Output: 4
Explanation: The number 4 appears only once. The numbers 1 and 2 each appear twice.
Example 3:
Input: [1]
Output: 1
Explanation: The array contains only one element, which is therefore the unique element.
Constraints
- The input array will contain at least one element.
- The numbers in the array will be within the range of standard integer types for your chosen programming language.
- Your solution should aim for an efficient time complexity.
Notes
Consider different approaches to solve this problem. Think about how you can keep track of elements you've seen and efficiently identify the one that doesn't have a pair. There are solutions that can achieve linear time complexity and constant space complexity.