Primer elemento que aparece un número par de veces en una array

Dada una array, encuentre el primer elemento que aparece un número par de veces en la array. Devuelve el elemento si existe, de lo contrario devuelve 0.
Ejemplos: 
 

Entrada: arr[] = {1, 5, 4, 7, 4, 1, 5, 7, 1, 5}; 
Salida: 4 
Explicación, 4 es el primer elemento que aparece un número par de veces.
Entrada: arr[] = {2, 4, 6, 8, 1, 6}; 
Salida: 6 
Explicación, 6 es el primer elemento que aparece un número par de veces

Una solución simple es considerar cada elemento uno por uno. Para cada elemento, comience a contar la frecuencia, el primer elemento cuyo recuento es par da el resultado. La complejidad temporal de esta solución es O(n ).
Una solución eficiente puede resolver este problema utilizando un mapa hash que tiene O(n) tiempo y O(n) espacio extra como: 
 

• Si a[i] no está presente en el mapa hash, insértelo en el mapa hash como par (a[i], falso).
• Si a[i] está presente en el mapa hash y el valor es verdadero, cámbielo a falso.
• Si a[i] está presente en el mapa hash y el valor es falso, cámbielo a verdadero.

// C++ code to find the first element
// that appears even number times
#include <bits/stdc++.h>
using namespace std;
int firstEven(int arr[], int n)
{
 
    unordered_map<int, bool> map1;
 
    for (int i = 0; i < n; i++)
    {
 
        // first time occurred
        if (map1.find(arr[i]) == map1.end())
            map1.insert(pair <int,bool> (arr[i],false));
 
        // toggle for repeated occurrence
        else
        {
            bool val = map1.find(arr[i])->second;
            if (val == true)
                map1.find(arr[i])->second = false;
            else
                map1.find(arr[i])->second = true;
        }
    }
 
    int j = 0;
    for (j = 0; j < n; j++)
    {
 
        // first integer with true value
        if (map1.find(arr[j])->second == true)
            break;
    }
 
    return arr[j];
}
 
// Driver code
int main()
{
    int arr[] = { 2, 4, 6, 8, 1, 6 };
    cout << firstEven(arr, 6);
    return 0;
}

// JAVA code to find the first element
// that appears even number times
import java.util.*;
class GFG {
    public static int firstEven(int arr[], int n)
    {
 
        HashMap<Integer, Boolean> map =
                 new HashMap<Integer, Boolean>();
 
        for (int i = 0; i < n; i++) {
 
            // first time occurred
            if (map.get(arr[i]) == null)
                map.put(arr[i], false);
             
            // toggle for repeated occurrence
            else {
                boolean val = map.get(arr[i]);
                if (val == true)
                    map.put(arr[i], false);
                else
                    map.put(arr[i], true);
            }
        }
 
        int j = 0;
        for (j = 0; j < n; j++) {
 
            // first integer with true value
            if (map.get(arr[j]) == true)
                break;
        }
 
        return arr[j];
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 2, 4, 6, 8, 1, 6 };
        int n = arr.length;
        System.out.println(firstEven(arr, n));
    }
}

# Python3 code to find the first element
# that appears even number times
def firstEven(arr, n):
 
    map1 = {}
    for i in range(0, n):
     
        # first time occurred
        if arr[i] not in map1:
            map1[arr[i]] = False
 
        # toggle for repeated occurrence
        else:
            map1[arr[i]] = not map1[arr[i]]
 
    for j in range(0, n):
     
        # first integer with true value
        if map1[arr[j]] == True:
            break
     
    return arr[j]
 
# Driver code
if __name__ == "__main__":
 
    arr = [2, 4, 6, 8, 1, 6]
    print(firstEven(arr, 6))
 
# This code is contributed
# by Rituraj Jain

// C# code to find the first element
// that appears even number times
using System;
using System.Collections.Generic;
 
class GFG
{
    static int firstEven(int []arr,
                         int n)
    {
        var map = new Dictionary<int,
                                 string>();
         
        var hash = new HashSet<int>(arr);
         
        foreach (int a in hash)
            map.Add(a, "null");
             
        for (int i = 0; i < n; i++)
        {
 
            // first time occurred
            if (map[arr[i]].Equals("null"))
                map[arr[i]] = "false";
             
            // toggle for repeated
            // occurrence
            else
            {
                string val = map[arr[i]];
                if (val.Equals("true"))
                    map[arr[i]] = "false";
                else
                    map[arr[i]] = "true";
            }
        }
 
        int j = 0;
        for (j = 0; j < n; j++)
        {
 
            // first integer with
            // true value
            if (map[arr[j]].Equals("true"))
                break;
        }
        return arr[j];
    }
 
    // Driver code
    static void Main()
    {
        int []arr = new int[]{ 2, 4, 6,
                               8, 1, 6 };
        int n = arr.Length;
        Console.Write(firstEven(arr, n));
    }
}
 
// This code is contributed by
// Manish Shaw(manishshaw1)

<script>
// Javascript code to find the first element
// that appears even number times
 
 
function firstEven(arr, n)
{
 
    let map1 = new Map();
 
    for (let i = 0; i < n; i++)
    {
 
        // first time occurred
        if (!map1.has(arr[i]))
            map1.set(arr[i],false);
 
        // toggle for repeated occurrence
        else
        {
            let val = map1.get(arr[i]);
            if (val == true)
                map1.set(arr[i], false);
            else
                map1.set(arr[i], true);
        }
    }
 
    let j = 0;
    for (j = 0; j < n; j++)
    {
 
        // first integer with true value
        if (map1.get(arr[j]) == true)
            break;
    }
 
    return arr[j];
}
 
// Driver code
 
    let arr = [ 2, 4, 6, 8, 1, 6 ];
    document.write(firstEven(arr, 6));
     
    // This code is contributed by gfgking.
</script>

6

Complejidad temporal: O(n) 
Espacio auxiliar: O(n)