Given an array, find the first element that appears even number of times in the array. It returns the element if exists otherwise returns 0.
Examples:
Input : arr[] = {1, 5, 4, 7, 4, 1, 5, 7, 1, 5};
Output : 4
Explanation, 4 is the first element that appears even number of times.Input : arr[] = {2, 4, 6, 8, 1, 6};
Output : 6
Explanation, 6 is the first element that appears even number of times
A Simple solution is to consider every element one by one. For every element, start counting the frequency, the first element whose count is even gives the result.
C++
// 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){ // Counting the frequency of every // element in array. for (int i=0;i<n;i++) { // Count variable to store the // frequency of arr[i] int count=0; for(int j=0;j<n;j++) { if(arr[i]==arr[j]) { count++; } } // checking if frequency is even or not if(count%2==0) { // Returning the first element // which appears even times return arr[i]; } } return 0;}// Driver codeint main(){ int arr[] = { 2, 4, 6, 8, 1, 6 }; cout << firstEven(arr, 6); return 0;}// This code is contributed by Utkarsh Kumar. |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG { static int firstEven(int[] arr, int n) { for (int i = 0; i < n; i++) { int count = 0; for (int j = 0; j < n; j++) { if (arr[i] == arr[j]) { count++; } } if (count % 2 == 0) { return arr[i]; } } return 0; } public static void main(String[] args) { int[] arr = {2, 4, 6, 8, 1, 6}; System.out.println(firstEven(arr, arr.length)); }}//This code is contributed by Nikhil Garg |
Python3
def firstEven(arr, n): # Counting the frequency of every # element in array. for i in range(n): # Count variable to store the # frequency of arr[i] count = 0 for j in range(n): if arr[i] == arr[j]: count += 1 # checking if frequency is even or not if count % 2 == 0: # Returning the first element # which appears even times return arr[i] return 0# Driver codearr = [2, 4, 6, 8, 1, 6]print(firstEven(arr, 6)) |
Javascript
// Javascript code to find the first element// that appears even number timesfunction firstEven(arr) { // Counting the frequency of every element in array. for (let i = 0; i < arr.length; i++) { // Count variable to store the frequency of arr[i] let count = 0; for (let j = 0; j < arr.length; j++) { if (arr[i] == arr[j]) { count++; } } // checking if frequency is even or not if (count % 2 == 0) { // Returning the first element which appears even times return arr[i]; } } return 0;}// Driver codeconst arr = [2, 4, 6, 8, 1, 6];console.log(firstEven(arr)); |
C#
using System;class Program{ static void Main(string[] args) { int[] arr = {2, 4, 6, 8, 1, 6}; Console.WriteLine(FirstEven(arr)); } static int FirstEven(int[] arr) { for (int i = 0; i < arr.Length; i++) { int count = 0; for (int j = 0; j < arr.Length; j++) { if (arr[i] == arr[j]) { count++; } } if (count % 2 == 0) { return arr[i]; } } return 0; }} |
Output
6
Time Complexity : O(n2 )
Space Complexity : O(1)
An Efficient solution can solve this problem using hash map having O(n) time and O(n) extra space as:
- Just store the frequency of all elements into the set
- Iterate the array again and check frequency and as soon as you get a element with even frequency return it, else return 0.
Implementation:
C++
// 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, int> map1; for (int i = 0; i < n; i++) { //storing frequency map1[arr[i]]++; } int j = 0; for (j = 0; j < n; j++) { //checking the frequency is even or not if(map1[arr[j]]%2==0)return arr[j]; } return 0;}// Driver codeint main(){ int arr[] = { 2, 4, 6, 8, 1, 6 }; cout << firstEven(arr, 6); return 0;} |
Java
// JAVA code to find the first element// that appears even number timesimport 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
# 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#
// C# code to find the first element// that appears even number timesusing 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) |
Javascript
<script>// Javascript code to find the first element// that appears even number timesfunction 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> |
Output
6
Complexity Analysis:
- Time Complexity: O(n)
- Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
