703421. Even occurring elements
Even Occurring Elements
Slug: even-occurring-elements4332
Difficulty: Basic
Id: 703421
Topic Tags: Arrays, Bit Magic, Data Structures
Company Tags: None
Summary
Given an array of integers, the task is to find all elements that occur an even number of times in the array. The problem involves arrays and bit manipulation.
Detailed Explanation
To solve this problem, we can use a simple approach with a hash map or dictionary. We iterate through the array, counting the occurrences of each element. Then, we iterate through the hash map and print out all elements that have an even count.
Here's the step-by-step breakdown:
- Create a hash map
countMapto store the frequency of each element in the array. - Iterate through the array and for each element:
- If the element is not present in
countMap, add it with a count of 1. - If the element is already present, increment its count by 1.
- If the element is not present in
- Iterate through
countMapand print out all elements that have an even count.
Time complexity: O(n), where n is the size of the array. We need to iterate through the array once to count the frequencies, then again to print out the result.
Space complexity: O(min(n, m)), where m is the maximum possible frequency of any element in the array (i.e., the number of unique elements). We need space to store the hash map.
Optimized Solutions
Java
import java.util.HashMap;
import java.util.Map;
public class Main {
public static void findEvenOccurringElements(int[] arr) {
Map<Integer, Integer> countMap = new HashMap<>();
for (int num : arr) {
if (!countMap.containsKey(num)) {
countMap.put(num, 1);
} else {
int count = countMap.get(num) + 1;
countMap.put(num, count);
}
}
for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
if (entry.getValue() % 2 == 0) {
System.out.println(entry.getKey());
}
}
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 2, 3, 4, 5, 6, 7};
findEvenOccurringElements(arr);
}
}