CareerCup

C# implementation, it runs in big O (N). More exactly, o (n + k) space and in o(n+k) time where k is the count of even numbers.

public static int GetFirstWithEvenAppearance(int[] numbers)
        {
            Dictionary<int, int> firstIndexes = new Dictionary<int, int>();
            HashSet<int> evenNumbers = new HashSet<int>();

            for (var i = 0; i < numbers.Length; ++i)
            {
                var number = numbers[i];

                if (false == firstIndexes.ContainsKey(number))
                    firstIndexes[number] = i; // the first apparition is not even
                else if (false == evenNumbers.Add (number)) // if we failed to add, then that means that it's not even
                    evenNumbers.Remove(number);
            }
            
            if (evenNumbers.Count > 0)
            {
                int minIndex = int.MaxValue;
                foreach (var even in evenNumbers)
                {
                    // getting the index!
                    var idx = firstIndexes[even];
                    if (idx < minIndex)
                        minIndex = idx;
                }

                return numbers[minIndex];
            }
            
            return -1;
        }

public static int GetFirstWithEvenAppearance(int[] arr)
        {
            arr = new int[] { 1, 2, 3, 4, 5, 1, 2, 3, 4, 5 };
            var hash = new Hashtable();

            foreach (var item in arr)
            {
                int count = hash[item] != null ? (int)hash[item] : 1;
                if (!hash.Contains(item))
                    hash[item] = count;
                else
                    hash[item] = count + 1;
            }

            foreach (int item in arr)
            {
                if ((int)hash[item] % 2 == 0)
                    return item;
            }
            return -1;
        }

package coding;

import java.util.HashMap;
import java.util.Map;

/**
 * Given an array, find the first element that appears an even number of times.
 *
 * Runtime : O(N)
 */
public class FirstElementWithEvenOccurences {

  public static void main(String[] args) {
    int[] array1 = {8, 9, 11, 9, 2, 11, 16, 16};
    int[] array2 = {8, 9, 7};

    System.out.println(getFirstElementWithEvenOccurences(array1));  // Prints 9
    System.out.println(getFirstElementWithEvenOccurences(array2));  // Prints null
  }

  private static Integer getFirstElementWithEvenOccurences(int[] array) {
    Map<Integer, Boolean> evenOccurencesMap = new HashMap<>();
    // Compute a map of elements and their even occurences bit
    for (int i = 0; i < array.length; i++) {
      Boolean evenBoolean = evenOccurencesMap.get(array[i]);
      if ( evenBoolean != null) {
        if (evenBoolean) {
          evenOccurencesMap.put(array[i], false);
        } else {
          evenOccurencesMap.put(array[i], true);
        }
      } else {
        evenOccurencesMap.put(array[i], false);
      }
    }

    // Look for the first one
    for (int i = 0; i < array.length; i++) {
      Boolean evenBoolean = evenOccurencesMap.get(array[i]);
      if (evenBoolean != null && evenBoolean) {
        return array[i];
      }
    }

    return null;
  }
}

#!/usr/bin/python
def look_for_parity(numbers):
numbers.sort()
parity = 0
previ = None
for i in numbers:
if i == previ:
parity ^= 1
elif parity:
return previ
previ = i
if parity:
return previ
return None

print(look_for_parity([-1,-1,3,0,2,4,5,1,5,5]))

#!/usr/bin/python
def look_for_parity(numbers):
	numbers.sort()
	parity = 0
	previ  = None
	for i in numbers:
		if i == previ:
			parity ^= 1
		elif parity:
			return previ
		previ = i
	if parity:
		return previ
	return None

print(look_for_parity([-1,-1,3,0,2,4,5,1,5,5]))

#!/usr/bin/python
def look_for_parity(numbers):
	numbers.sort()
	parity = 0
	previ  = None
	for i in numbers:
		if i == previ:
			parity ^= 1
		elif parity:
			return previ
		previ = i
	if parity:
		return previ
	return None

print(look_for_parity([-1,-1,3,0,2,4,5,1,5,5]))

package coding;

import java.util.HashMap;
import java.util.Map;

/**
 * Given an array, find the first element that appears an even number of times.
 *
 * Runtime : O(N)
 */
public class FirstElementWithEvenOccurences {

  public static void main(String[] args) {
    int[] array1 = {8, 9, 11, 9, 2, 11, 16, 16};
    int[] array2 = {8, 9, 7};

    System.out.println(getFirstElementWithEvenOccurences(array1));  // Prints 9
    System.out.println(getFirstElementWithEvenOccurences(array2));  // Prints null
  }

  private static Integer getFirstElementWithEvenOccurences(int[] array) {
    Map<Integer, Boolean> evenOccurencesMap = new HashMap<>();
    // Compute a map of elements and their even occurences bit
    for (int i = 0; i < array.length; i++) {
      Boolean evenBoolean = evenOccurencesMap.get(array[i]);
      if ( evenBoolean != null) {
        if (evenBoolean) {
          evenOccurencesMap.put(array[i], false);
        } else {
          evenOccurencesMap.put(array[i], true);
        }
      } else {
        evenOccurencesMap.put(array[i], false);
      }
    }

    // Look for the first one
    for (int i = 0; i < array.length; i++) {
      Boolean evenBoolean = evenOccurencesMap.get(array[i]);
      if (evenBoolean != null && evenBoolean) {
        return array[i];
      }
    }

    return null;
  }

}

package coding;

import java.util.HashMap;
import java.util.Map;

/**
* Given an array, find the first element that appears an even number of times.
*
* Runtime : O(N)
*/
public class FirstElementWithEvenOccurences {

public static void main(String[] args) {
int[] array1 = {8, 9, 11, 9, 2, 11, 16, 16};
int[] array2 = {8, 9, 7};

System.out.println(getFirstElementWithEvenOccurences(array1)); // Prints 9
System.out.println(getFirstElementWithEvenOccurences(array2)); // Prints null
}

private static Integer getFirstElementWithEvenOccurences(int[] array) {
Map<Integer, Boolean> evenOccurencesMap = new HashMap<>();
// Compute a map of elements and their even occurences bit
for (int i = 0; i < array.length; i++) {
Boolean evenBoolean = evenOccurencesMap.get(array[i]);
if ( evenBoolean != null) {
if (evenBoolean) {
evenOccurencesMap.put(array[i], false);
} else {
evenOccurencesMap.put(array[i], true);
}
} else {
evenOccurencesMap.put(array[i], false);
}
}

// Look for the first one
for (int i = 0; i < array.length; i++) {
Boolean evenBoolean = evenOccurencesMap.get(array[i]);
if (evenBoolean != null && evenBoolean) {
return array[i];
}
}

return null;
}

}

package coding;

import java.util.HashMap;
import java.util.Map;

/**
* Given an array, find the first element that appears an even number of times.
*
* Runtime : O(N)
*/
public class FirstElementWithEvenOccurences {

public static void main(String[] args) {
int[] array1 = {8, 9, 11, 9, 2, 11, 16, 16};
int[] array2 = {8, 9, 7};

System.out.println(getFirstElementWithEvenOccurences(array1)); // Prints 9
System.out.println(getFirstElementWithEvenOccurences(array2)); // Prints null
}

private static Integer getFirstElementWithEvenOccurences(int[] array) {
Map<Integer, Boolean> evenOccurencesMap = new HashMap<>();
// Compute a map of elements and their even occurences bit
for (int i = 0; i < array.length; i++) {
Boolean evenBoolean = evenOccurencesMap.get(array[i]);
if ( evenBoolean != null) {
if (evenBoolean) {
evenOccurencesMap.put(array[i], false);
} else {
evenOccurencesMap.put(array[i], true);
}
} else {
evenOccurencesMap.put(array[i], false);
}
}

// Look for the first one
for (int i = 0; i < array.length; i++) {
Boolean evenBoolean = evenOccurencesMap.get(array[i]);
if (evenBoolean != null && evenBoolean) {
return array[i];
}
}

return null;
}

}

package coding;

import java.util.HashMap;
import java.util.Map;

/**
 * Given an array, find the first element that appears an even number of times.
 *
 * Runtime : O(N)
 */
public class FirstElementWithEvenOccurences {

  public static void main(String[] args) {
    int[] array1 = {8, 9, 11, 9, 2, 11, 16, 16};
    int[] array2 = {8, 9, 7};

    System.out.println(getFirstElementWithEvenOccurences(array1));  // Prints 9
    System.out.println(getFirstElementWithEvenOccurences(array2));  // Prints null
  }

  private static Integer getFirstElementWithEvenOccurences(int[] array) {
    Map<Integer, Boolean> evenOccurencesMap = new HashMap<>();

    // Compute a map of elements and their even occurences bit
    for (int i = 0; i < array.length; i++) {
      Boolean evenBoolean = evenOccurencesMap.get(array[i]);
      if ( evenBoolean != null) {
        if (evenBoolean) {
          evenOccurencesMap.put(array[i], false);
        } else {
          evenOccurencesMap.put(array[i], true);
        }
      } else {
        evenOccurencesMap.put(array[i], false);
      }
    }

    // Look for the first one
    for (int i = 0; i < array.length; i++) {
      Boolean evenBoolean = evenOccurencesMap.get(array[i]);
      if (evenBoolean != null && evenBoolean) {
        return array[i];
      }
    }

    return null;
  }
}

package coding;

import java.util.HashMap;
import java.util.Map;

/**
 * Given an array, find the first element that appears an even number of times.
 *
 * Runtime : O(N)
 */
public class FirstElementWithEvenOccurences {

  public static void main(String[] args) {
    int[] array1 = {8, 9, 11, 9, 2, 11, 16, 16};
    int[] array2 = {8, 9, 7};

    System.out.println(getFirstElementWithEvenOccurences(array1));  // Prints 9
    System.out.println(getFirstElementWithEvenOccurences(array2));  // Prints null
  }

  private static Integer getFirstElementWithEvenOccurences(int[] array) {
    Map<Integer, Boolean> evenOccurencesMap = new HashMap<>();
    // Compute a map of elements and their even occurences bit
    for (int i = 0; i < array.length; i++) {
      Boolean evenBoolean = evenOccurencesMap.get(array[i]);
      if ( evenBoolean != null) {
        if (evenBoolean) {
          evenOccurencesMap.put(array[i], false);
        } else {
          evenOccurencesMap.put(array[i], true);
        }
      } else {
        evenOccurencesMap.put(array[i], false);
      }
    }

    // Look for the first one
    for (int i = 0; i < array.length; i++) {
      Boolean evenBoolean = evenOccurencesMap.get(array[i]);
      if (evenBoolean != null && evenBoolean) {
        return array[i];
      }
    }

    return null;
  }
}

c++ code:

void even_occurance_in_array(void)
{
	vector<int> arr;
	int n;
	int counter;
	cout << "\nEnter array numbers:(Insert -1 to exit)\n";//assumed -1 can not be in array. It can be replaced with any invalid number
	do{
		cin >> n;
		if (n != -1)
			arr.push_back(n);
	} while (n != -1);
	
	for (int i = 0; i < arr.size(); i++)
	{
		counter = 1;
		for (int j = i + 1; j < arr.size() && (arr[i] != -1); j++)
		{
			if ((arr[j] != -1) && (arr[i] == arr[j]))
			{
				counter++;
				arr[j] = -1;
			}
		}
		if (counter % 2 == 0)
		{
			cout << "First number " << arr[i] << " has even occurance in the array" << endl;
			break;
		}
	}

import java.util.HashMap;

public class Pyramid {

	public static void main(String[] args) {
		int a[] = { 4, 5, 6, 7, 8, 9, 5, 5, 3, 4, 12, 5 };
		HashMap<Integer, Boolean> hm = new HashMap<Integer, Boolean>();
		for (int x : a) {
			
			if (hm.get(x) == null) {
				hm.put(x, false);
			} else {
				Boolean b = hm.get(x);
				if (b == true)
					hm.put(x, false);
				else
					hm.put(x, true);
			}
		}
		System.out.println("here");
		for (int y : a) {
			if (hm.get(y)) {
				System.out.println("First Even " + y);
				break;
			}
		}

	}
}

C++:

void even_occurance_in_array(void)
{
	vector<int> arr;
	int n;
	int counter;
	cout << "\nEnter array numbers:(Insert -1 to exit)\n";//assumed -1 can not be in array. It can be replaced with any invalid number
	do{
		cin >> n;
		if (n != -1)
			arr.push_back(n);
	} while (n != -1);
	
	for (int i = 0; i < arr.size(); i++)
	{
		counter = 1;
		for (int j = i + 1; j < arr.size() && (arr[i] != -1); j++)
		{
			if ((arr[j] != -1) && (arr[i] == arr[j]))
			{
				counter++;
				arr[j] = -1;
			}
		}
		if (counter % 2 == 0)
		{
			cout << "First number " << arr[i] << " has even occurance in the array" << endl;
			break;
		}
	}

}

getFirstEvenIntegerInArray: function(array) {
    var hash = {};
	for(var i = 0; i  < array.length; i++) {
	  if(hash.hasOwnProperty(array[i])) {
	    hash[array[i]].count ++;
	  } else {
	     hash[array[i]] = { count: 1 };
	  }
	}
	
	for(var i = 0; i < array.length; i ++) {
	  if(hash[array[i]].count % 2 === 0)
	    return array[i];
	}
	return null;
  }

For those of you using Hashes. You might be said that according to the Java/OtherLanguage documentation a Hash does not guarantee the order in which you retrieve the data. So, probably for very large lists, the solution might not be correct.

int getFirstNoWithEvenOcc(int *arr, int n)
{
int i,j, count;
for(i = 0; i < n; i++)
{
count = 1;
for(j= i + 1; j < n; j++)
{
if(arr[i] == arr[j])
count++;
}
if(count % 2 == 0)
return arr[i];
}
}

int getFirstNoWithEvenOcc(int *arr, int n)
{
int i,j, count;
for(i = 0; i < n; i++)
{
count = 1;
for(j= i + 1; j < n; j++)
{
if(arr[i] == arr[j])
count++;
}
if(count % 2 == 0)
return arr[i];
}
}

int getFirstNoWithEvenOcc(int *arr, int n)
{
int i,j, count;
for(i = 0; i < n; i++)
{
count = 1;
for(j= i + 1; j < n; j++)
{
if(arr[i] == arr[j])
count++;
}
if(count % 2 == 0)
return arr[i];
}
}

import random

n = 20
a = []
for _ in range(n):
    a.append(random.randint(1, 6))
print a

t = {}
for i in a:
    t[i] = t[i] * -1 if i in t else -1

solution_found = False
for i in a:
    if t[i] > 0:
        print i
        exit(0)

print 'no solution'

public class FirstEvenOccurences {
public static void main(String args[]){
int[] arr = {1,4,3,5,6,2,4,2};
HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();

for(int element: arr){
if(map.get(element) == null)
map.put(element, false);
else{
if(map.get(element) == true)
map.put(element, false);
else
map.put(element, true);
}
}

for(int element: arr){
if(map.get(element) == true){
System.out.println("First even occurence: " + element);
break;
}
}

}
}

I think firstly we should ask what type of elements are in array, if it is small integer numbers, we can create a boolean array X with size equal to maximum element, and iterate through given array and make X[arr[i] - 1] = true if its false, otherwise return arr[i].

If the length of given array is greater than the maximum element in array and if elements are nonnegative integers, we can just iterate through given array and check if a[i] < 0 then return i, else a[a[i]] = -a[a[i]],

if elements are not integers or contain negative numbers etc, we can use hashmap to solve it.

Easy python code using hash table. Complexity O(n)

def FirstEvenElement(lst):
    d = {}
    for i in lst:
        d[i] = d.get(i, 0) + 1
    for j in lst:
        if d[j] % 2 == 0:
            return j

print(FirstEvenElement([1, 3, 1, 3, 2, 1]))

package com.concurrency.pkg;

import java.util.LinkedHashMap;
import java.util.Map;

public class FirstElementWithEvenOccurences {

public static void main(String[] args) {
int[] array1 = { 8, 9, 11, 2, 11, 11, 16, 9, 16 };

System.out.println(getFirstElementWithEvenOccurences(array1)); // Prints
// 9
}

private static Integer getFirstElementWithEvenOccurences(int[] array) {
Map<Integer, Integer> allOcurrence = new LinkedHashMap<>();
for (int i = 0; i < array.length; i++) {
Integer keyValue = new Integer(array[i]);
Integer value = allOcurrence.get(keyValue);
value = null != value ? value + keyValue : keyValue;
allOcurrence.put(keyValue, value);
}
Integer parityElement = null;
for (Integer key : allOcurrence.keySet()) {
int div = (allOcurrence.get(key) / key);
if ((div & 1) != 1) {
parityElement = key;
break;
}
}

return parityElement;

}
}

(Java) This function returns all the numbers that appear an even number of times in the array. Time complexity = O(N), space complexity = O(N)

public Set<Integer> evenTimes(List<Integer> arr) {
	Set<Integer> result = new HashSet<>();
	for (int n : arr) {
		if (result.contains(n)) { result.remove(n): }
		else { result.add(n): }
	}
	return result;
}

import java.util.LinkedHashMap;
import java.util.Map;

public class SearchingElement {

	public static void main(String[] args){
		LinkedHashMap<Integer,Integer>  lh = new LinkedHashMap<Integer, Integer>();
		int[] a ={1,2,3,4,5,6,2,3,2,4,3,2,3};
		for(int element:a){
			if(lh.get(element)==null){
				lh.put(element,1);
			}
			else
				lh.put(element,lh.get(element)+1);
		}
		//for (Map.Entry<Integer,Integer> e: lh.entrySet()){
			for (Map.Entry<Integer, Integer> entry : lh.entrySet()){
				if(entry.getValue()%2==0)
					System.out.println(entry.getKey());
			
		}
	}

}

//First even occurence in a array
//Using visited array
#include <iostream>
using namespace std;
# define size 256

int firstEven(int a[],int n){
int num;
int arr[size];
for(int i=0;i<size;i++){
	arr[i]=0;
}
	for(int j=0;j<n;j++){
		if(arr[a[j]]==0) arr[a[j]]=1;
		else arr[a[j]]+=1;

		if (arr[a[j]]==2) {num=a[j]; break;}
	}
	
return num;
}

int main(){
	
	int a[10] = {1,2,3,2,2,3,2};
	int n = sizeof(a)/sizeof(a[0]);
	int num = firstEven(a,n);
	cout<<num;
}

//First even occurence in a array
//Using visited array
#include <iostream>
using namespace std;
# define size 256

int firstEven(int a[],int n){
int num;
int arr[size];
for(int i=0;i<size;i++){
	arr[i]=0;
}
	for(int j=0;j<n;j++){
		if(arr[a[j]]==0) arr[a[j]]=1;
		else arr[a[j]]+=1;

		if (arr[a[j]]==2) {num=a[j]; break;}
	}
	
return num;
}

int main(){
	
	int a[10] = {1,2,3,2,2,3,2};
	int n = sizeof(a)/sizeof(a[0]);
	int num = firstEven(a,n);
	cout<<num;
}

Isn't this simply the first element which is duplicated?

Isn't this simply the first element which is duplicated?

public static int findFirstEvenOccuringNumber(int[] numbers) {

    Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    
    for(int number : numbers) {
    
        if(!map.containsKey(number)) {
                    map.put(number,1);
        } else {
                    map.put(number, map.get(number) + 1);
                    if(map.get(number)%2 == 0) {
                        return number;
                    }    
        }   
    }
    return -1;
}

public static int findFirstEvenOccuringNumber(int[] numbers) {

    Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    
    for(int number : numbers) {
    
        if(!map.containsKey(number)) {
                    map.put(number,1);
        } else {
                    map.put(number, map.get(number) + 1);
                    if(map.get(number)%2 == 0) {
                        return number;
                    }    
        }   
    }
    return -1;
}

public static int findFirstEvenOccuringNumber(int[] numbers) {

    Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    
    for(int number : numbers) {
    
        if(!map.containsKey(number)) {
                    map.put(number,1);
        } else {
                    map.put(number, map.get(number) + 1);
                    if(map.get(number)%2 == 0) {
                        return number;
                    }    
        }   
    }
    return -1;
}

public static int findFirstEvenOccuringNumber(int[] numbers) {

    Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    
    for(int number : numbers) {
    
        if(!map.containsKey(number)) {
                    map.put(number,1);
        } else {
                    map.put(number, map.get(number) + 1);
                    if(map.get(number)%2 == 0) {
                        return number;
                    }    
        }   
    }
    return -1;
}

We create a hash map with the numbers and have a bit value to each number. So when the number is added for the first time bit will be 1 and then every time we find that number again we will toggle the bit. Then once the hashMap is created will parse through array once again whichever element has bit as 0 will be our number.

HashMap<Integer, boolean>

for each number in array{
if does not exists in hash map then add (num, true)
else toggle the bit associated(if 1 the 0, vice versa)
}

for each number in array{
if bit is 0 in hashmap then return number
}

The only reason I used bit is for storing the even not even part and as it occupies only one bit it saves space as well.

import java.util.LinkedHashMap;
import java.util.Objects;
import java.util.Optional;
import java.util.Set;

public class ArrayUtil {
	public static Optional<Integer> getFirstEvenNumber(int[] arr) {
		if (Objects.isNull(arr))
			throw new NullPointerException("Array Shouldn't be null");

		LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();

		for (int data : arr) {
			if (!map.containsKey(data)) {
				map.put(data, 1);
				continue;
			}

			map.put(data, map.get(data) + 1);
		}
		
		Set<Integer> keys = map.keySet();

		for (int key : keys) {
			if (map.get(key) % 2 == 0) {
				return Optional.of(key);
			}
		}

		return Optional.empty();

	}
}