Problem

Given an integer array, where exactly one element occurs an even number of times and all others occur an odd number of times, find the element with even occurrences.

Examples

Example 1

1
2
3

Input: [1, 2, 2, 2, 3, 4, 4, 4, 5, 6, 7, 7, 4, 4]
Output: 7
Explanation: 7 appears 2 times (even), all others appear odd times.

Constraints

  • 1 <= n <= 10^5
  • Array elements are integers (may be negative or positive)
  • Exactly one element occurs an even number of times, all others occur odd times

Solution

Method 1 – Hash Map Frequency Count

Intuition

Count the frequency of each element using a hash map. The only element with an even count is the answer.

Approach

  1. Initialize an empty hash map to count occurrences.
  2. For each element in the array, increment its count in the map.
  3. Iterate through the map and return the element with an even count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

#include <unordered_map>
class Solution {
public:
  int findEven(const vector<int>& arr) {
    unordered_map<int, int> freq;
    for (int x : arr) freq[x]++;
    for (auto& [num, cnt] : freq) if (cnt % 2 == 0) return num;
    return -1; // not found
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func findEven(arr []int) int {
  freq := make(map[int]int)
  for _, x := range arr {
    freq[x]++
  }
  for num, cnt := range freq {
    if cnt%2 == 0 {
      return num
    }
  }
  return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

import java.util.*;
class Solution {
  public int findEven(int[] arr) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int x : arr) freq.put(x, freq.getOrDefault(x, 0) + 1);
    for (var entry : freq.entrySet())
      if (entry.getValue() % 2 == 0) return entry.getKey();
    return -1;
  }
}
1
2
3
4
5
6
7
8
9

class Solution:
  def findEven(self, arr: list[int]) -> int:
    freq: dict[int, int] = {}
    for x in arr:
      freq[x] = freq.get(x, 0) + 1
    for num, cnt in freq.items():
      if cnt % 2 == 0:
        return num
    return -1

Complexity

  • ⏰ Time complexity: O(n), because we scan the array and then the map.
  • 🧺 Space complexity: O(n), for the hash map.