How to Find the Element that Appears Once in an Array

Finding the element that appears only once in an array where all other elements appear twice is a common problem in coding interviews and programming challenges. In this article, we'll discuss four approaches to solve this problem: one using a brute force approach, another using hashing, a third using a map, and the optimal approach using XOR.

Solution 1: Brute Force Approach (using Nested Loop)

This method involves using a nested loop to find the element that appears only once.

Implementation:

// Solution-1: Brute Force Approach (using Nested Loop)
// Time Complexity: O(n*n)
// Space Complexity: O(1)
int getSingleElement(vector<int> &arr, int n)
{
    // Loop for selecting elements
    for (int i = 0; i < n; i++)
    {
        // Selected element
        int num = arr[i];

        int counter = 0;

        // Find the occurrence using Linear Search
        for (int j = 0; j < n; j++)
        {
            if (arr[j] == num)
            {
                counter++;
            }
        }

        // If the occurrence is 1, return that element
        if (counter == 1)
        {
            return num;
        }
    }

    // In case no element appears once
    return -1;
}

Logic:

1. Nested Loop: Use an outer loop to iterate through each element of the array. Use an inner loop to count the occurrences of the selected element.

2. Check for Single Occurrence: If the count of the selected element is 1, return that element.

Time Complexity: O(n*n)

• Explanation: Each element in the array is compared with every other element, resulting in a nested loop.

Space Complexity: O(1)

• Explanation: No additional space is used apart from variables for counting.

Example:

• Input: arr = [4, 3, 2, 4, 1, 3, 2]

• Output: 1

• Explanation: The element 1 appears only once in the array.

---

Solution 2: Better Approach (using Hashing)

This method uses hashing to find the element that appears only once.

Implementation:

// Solution-2: Better Approach 1 (using Hashing)
// Time Complexity: O(3n) ~ O(n)
// Space Complexity: O(maxElement+1)
int getSingleElement(vector<int> &arr, int n)
{
    // Find the maximum element
    int maxElement = arr[0];
    for (int i = 0; i < n; i++)
    {
        if (arr[i] > maxElement)
        {
            maxElement = arr[i];
        }
    }

    // Hash Array of size maxElement + 1
    vector<int> hash(maxElement + 1, 0);

    // Hash the array
    for (int i = 0; i < n; i++)
    {
        hash[arr[i]]++;
    }

    // Find the single element and return that
    for (int i = 0; i < n; i++)
    {
        if (hash[arr[i]] == 1)
        {
            return arr[i];
        }
    }

    // In case no element appears once
    return -1;
}

Logic:

1. Find Maximum Element: Traverse the array to find the maximum element.

2. Hash the Array: Create a hash array of size maxElement + 1 and count the occurrences of each element. maxElement is the maximum element in the array.

3. Check for Single Occurrence: Traverse the hash array to find the element with a count of 1.

Time Complexity: O(3n) ~ O(n)

• Explanation: The array is traversed three times (to find the maximum element, hash the array, and find the single element).

Space Complexity: O(maxElement+1)

• Explanation: Additional space is used for the hash array. Here, maxElement is the maximum element in the array.

Example:

• Input: arr = [4, 3, 2, 4, 1, 3, 2]

• Output: 1

• Explanation: The element 1 appears only once in the array.

---

Solution 3: Better Approach (using Map for Hashing)

This method uses a map to find the element that appears only once.

Implementation:

// Solution-3: Better Approach 2 (using Map for Hashing)
// Time Complexity: O(n * log M) + O(M)
// Space Complexity: O(M)
int getSingleElement(vector<int> &arr, int n)
{
    // Declare the Map
    map<int, int> track;

    // Hash the array
    for (int i = 0; i < n; i++)
    {
        track[arr[i]]++;
    }

    // Find the single element and return that
    for (auto it : track)
    {
        if (it.second == 1)
        {
            return it.first;
        }
    }

    // In case no element appears once
    return -1;
}

Logic:

1. Hash the Array: Use a map to count the occurrences of each element.

2. Check for Single Occurrence: Traverse the map to find the element with a count of 1.

Time Complexity: O(n * log M) + O(M)

• Explanation: The array is hashed in O(n * log M) time and then traversed in O(M) time. Here, M is the size of the map (in this case, M = (n/2)+1) and n = size of the array. Note: [ It takes O(log M) time to access an element in the map ]

Space Complexity: O(M)

• Explanation: Additional space is used for the map. Here, M is the size of the map (in this case, M = (n/2)+1) and n = size of the array.

Example:

• Input: arr = [4, 3, 2, 4, 1, 3, 2]

• Output: 1

• Explanation: The element 1 appears only once in the array.

---

Solution 4: Optimal Approach (using XOR)

This method uses XOR to find the element that appears only once.

Implementation:

// Solution-4: Optimal Approach (using XOR)
// Time Complexity: O(n)
// Space Complexity: O(1)
int getSingleElement(vector<int> &arr, int n)
{
    int appearsOnce = 0;

    // XOR all the elements
    for (int i = 0; i < n; i++)
    {
        appearsOnce ^= arr[i];
    }

    return appearsOnce;
}

Logic:

1. XOR All Elements: XOR all the elements of the array. The elements appearing twice will cancel out, leaving the element that appears once. This approach leverages the property a ^ a = 0 and a ^ 0 = a.

Time Complexity: O(n)

• Explanation: The array is traversed once.

Space Complexity: O(1)

• Explanation: No additional space is used.

Example:

• Input: arr = [4, 3, 2, 4, 1, 3, 2]

• Output: 1

• Explanation: The element 1 appears only once in the array.

---

Comparison

• Brute Force Approach:

  • Pros: Simple and straightforward.
  • Cons: Inefficient for large arrays due to O(n*n) time complexity.

• Better Approach (using Hashing):

  • Pros: More efficient than brute force with O(3n) ~ O(n) time complexity.
  • Cons: Requires additional space for the hash array.

• Better Approach (using Map for Hashing):

  • Pros: Efficient with O(n * log M) + O(M) time complexity.
  • Cons: Requires additional space for the map for hashing.

• Optimal Approach (using XOR):

  • Pros: Highly efficient with O(n) time complexity and no additional space usage.
  • Cons: Slightly more complex to understand but very efficient.

Edge Cases

• Empty Array: Returns -1 as there are no elements to check.

• No Single Element: Returns -1 if no element appears exactly once.

• All Elements are the Same: Returns -1 if no unique element exists.

Additional Notes

• Efficiency: The XOR technique is the most time-efficient and space-efficient, making it preferable for large arrays.

• Practicality: The choice of approach depends on the specific constraints and requirements of the problem, such as array size and available memory.

Conclusion

Finding the element that appears once in an array where all other elements appear twice can be efficiently achieved using various approaches. The optimal choice depends on the specific constraints and requirements of the problem, with the XOR method being the most efficient in terms of both time and space.

---