CareerCup

Here is a O(n) time and O(1) space solution. It requires 256 MB of constant memory on my machine though :)). What it does is to represent all possible numbers (expressible with an int) in two arrays (bit arrays to be exact). Where one is to keep if a number does exist and one is to keep if the number is even or odd. After passing through the list and setting these arrays accordingly, it analyzes these two arrays to find out numbers that exists and even.

The reason to keep an array to determine whether a number exists is simply because every number that doesn't exist in the list occurs 0 times which is even. I don't think who asks this question wants us to print millions of numbers therefore to rule out that condition we should utilise it.

While it may seem like cheating since we are using a huge array and say “that is constant size and i can do whatever i want as long as it is constant”, i don’t think this is an invalid answer. In fact i think it is perfectly feasible and maybe your only option if you have TBs, PBs of data to process. Isn’t that why we do asymptotic analysis in the first place. What you have to do is to feed data as 4GB chunks to process function (since it takes an unsigned int as size parameter).

#include <iostream>

using namespace std;

typedef unsigned int uint;
#define BITS_IN_A_BYTE 8
// Can use CHAR_BITS to be more precise
#define BITS_IN_A_UINT (sizeof(uint) * BITS_IN_A_BYTE)
// 32 bits on my machine
#define BIT_VECTOR_SIZE ((static_cast<uint>(-1)/BITS_IN_A_UINT)+1)
// 128MB on my machine

uint doesExist[BIT_VECTOR_SIZE];
uint isOdd[BIT_VECTOR_SIZE];

void decodeIndex(const uint num, uint& intIndex, uint& bitIndex) {
	intIndex = num / BITS_IN_A_UINT;
	bitIndex = num % BITS_IN_A_UINT;
}

void set(const uint num, uint* const bitVector) {
	uint intIndex, bitIndex;
	decodeIndex(num, intIndex, bitIndex);
	bitVector[intIndex] |= 1 << bitIndex;
}

void toggle(const uint num, uint* const bitVector) {
	uint intIndex, bitIndex;
	decodeIndex(num, intIndex, bitIndex);
	bitVector[intIndex] ^= 1 << bitIndex;
}

void process(const uint * const array, uint size) {
	for(uint i=0;i<size;i++) {
		set(array[i], doesExist);
		toggle(array[i], isOdd);
	}
}

void findEvenOccurrences(void callback(uint num)) {
	for(uint i=0;i<BIT_VECTOR_SIZE;i++) {
		uint isExistingAndEven = doesExist[i] ^ isOdd[i];
		if(isExistingAndEven) {
			for(uint b=0;b<BITS_IN_A_UINT;b++) {
				if(isExistingAndEven & 1) {
					callback(i*BITS_IN_A_UINT + b);
				}
				isExistingAndEven >>= 1;
			}
		}
	}
}

void printerCallback(uint num) {
	cout << num << endl;
}

int main() {
	const uint testVectorChunk1[] = {1,3,4294967295,1,7,3,8,1000000,3,4294967295,1,1,1000000,8,8};
	const uint testVectorChunk1Size = 15;

	const uint testVectorChunk2[] = {100000000,75,100000000,75,100000000,75,100000000};
	const uint testVectorChunk2Size = 15;

	cout << "Processing..." << endl;
	process(testVectorChunk1, testVectorChunk1Size);
	process(testVectorChunk2, testVectorChunk2Size);
	findEvenOccurrences(printerCallback);
	cout << "Finished..." << endl;
}

My solution is to use 2 Hash maps so that when count turns to even - you delete from "odd map" and add to "even map". Algorithm complexity is O(n) - due to every operation on hash map is O(1).

public class SS {

    static class EvenCount {

        public Set<Integer> evenTimes(int[] input) {
            HashMap<Integer, Integer> odd = new HashMap<Integer, Integer>();
            HashMap<Integer, Integer> even = new HashMap<Integer, Integer>();

            for (int i = 0; i < input.length; ++i) {
                int current = input[i];
                Integer oddCurrent = odd.get(current);                   // 1
                Integer evenCurrent = even.get(current);                 // 1

                if (notOdd(oddCurrent) && notEven(evenCurrent)) {
                    odd.put(current, 1);                                 // 1
                } else if (notOdd(oddCurrent)) {
                    odd.put(current, evenCurrent + 1);                       // 1
                    even.remove(current);                                     // 1
                } else if (notEven(evenCurrent)) {
                    even.put(current, oddCurrent + 1);                            // 1
                    odd.remove(current);                                            // 1
                }
            }

            return even.keySet();
        }

        private boolean notOdd(Integer integer) {
            return integer == null;
        }

        private boolean notEven(Integer integer) {
            return integer == null;
        }

    }

    public static void main(String[] args) {
        System.out.println(new EvenCount().evenTimes(new int[]{1, 2, 2, 3, 3}));

    }
}

Java solution, returns the number which occurs even number of times.

public Integer findItemWEvenOcc(int[] in)
	{
		Map<Integer, Integer> myMap=new HashMap<Integer,Integer>();
		
		for(int i : in)
		{
			if(!myMap.containsKey(i))
			{
				myMap.put(i, 1);
			}
			else
			{
				int numberOfOccurance=myMap.get(i);
				numberOfOccurance++;
				myMap.put(i, numberOfOccurance);
			}
		}
		
		for(Map.Entry<Integer, Integer> kv : myMap.entrySet())
		{
			if(kv.getValue()%2==0)
			{
				return kv.getKey();
			}
		
		}
		return null;
		
	}

{{

package com.algo;

public class EvenCount {

public int eventCount(int[] a) {
int output = 0;
for (int i = 0; i < a.length; i++) {
output = output ^ a[i];
}
return output;
}

public static void main(String[] args) {

int[] a = { 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3 };
EvenCount count = new EvenCount();
System.out.println(count.eventCount(a));

}
}

}}

1st Approach: Using sorting and then iterating over the array to see which element has an even count.
Time: O(n lg n)
Space: O(1)

2nd Approach: Use a hashmap to keep a count of the number of times a number occurs. Then iterate over the hashmap to find which number has occured even number of times.
Time: O(n)
Space: O(n) (Worst case: could be if all the elements appear once except one that occurs twice which leads to a space requirement of O(n))

However an approach which could give the correct result in O(n) time and O(1) space is the one i guess is required in this case.

first sort the array and run below code

public void FindEvenOccurance(int[] arr,int size)
{
int count,j;
for(int i=0;i<size;i++)
{
count = 1;
j=i+1;
while(j<size && arr[j]==arr[i])
{
count++;
j++;
}
if(count %2==0)
Console.WriteLine("Number"+ arr[i]);
i = j - 1;
}
}

(function() {
	'use strict';
	var checkOddAry = function(inputAry) {
		var numObj = {};
		var i = 0;
		var length = inputAry.length;

		for (i = 0; i < length; i++) {
			numObj[inputAry[i]] = !numObj[inputAry[i]];
		}

		for (i in numObj) {
			if (numObj.hasOwnProperty(i)) {
				if (numObj[i] === false) {
					return i;
				}
			}
		}

		return false;
	};

	var inputAry = [1, 1, 2, 2, 3, 4, 5, 5, 4, 1, 2, 3, 4, 5];

	console.log(checkOddAry(inputAry));

	inputAry = [];

	console.log(checkOddAry(inputAry));

	inputAry = [1, 2, 1];

	console.log(checkOddAry(inputAry));
})();

My Solution in python. Time complexity is O(n)

testArr = [1,1,1,4,4,4,9,5,9,6,9,10,8,10]

def returnEven(arr):
    lenofArr = len(arr)
    """
    initilize data
    """
    storeCount = {}
    seen = set()
    current = arr[0]
    storeCount[current] = 1
    seen.add(current)

    for i in range(1, lenofArr):
        if arr[i] == current:
            storeCount[current] += 1
        else:
            current = arr[i]
            if current in seen:
                storeCount[current] +=1
            else:
                seen.add(current)
                storeCount[current] = 1

    for k,v in storeCount.items():
        if v % 2 == 0:
            return k

    return None
        
            


		
print(returnEven(testArr))
10

import java.util.*;
public class HelloWorld{

     public static void main(String []args){
        int[] a={2,2,2,3,3,3,4,4,5,5,5,6,6,6};
           ArrayList<Integer> Num=new ArrayList<Integer>();
           ArrayList<Integer> Count=new ArrayList<Integer>();
           Num.add(a[0]);
           int count=1;
            
           for(int i=1;i<a.length;i++)
           {
               if(a[i]==a[0])
               count++;
           }
           Count.add(count);
  
           for(int i=0;i<a.length;i++)
           {
               
               if(Num.contains(a[i]))
               {
                   continue;
               }else // if not contain. add new node for a[i], count counts from i~length-1
               {
                   Num.add(a[i]);
                   count=1;
                   for(int j=i+1;j<a.length;j++)
                   {
                       if(a[j]==a[i])
                       count++;
                   }
                   Count.add(count);
               }
           }
           for(int i=0;i<Count.size();i++)
           {
               if(Count.get(i)%2==0)
               {
                  System.out.print(Num.get(i));
                  break;
               }
           }
           
                
       
     }
}

If we use a Set, we can do this at O(n).

If str is not existed -> add
if str is existed -> delete

That is, odd number occurrence will lead "existence". However, even number occurrence will lead "not existence" in a set.

public static Optional<String> findEvenNumberExistedWord(String[] arr) {
	Set<String> cache = new HashSet<>();
	
	for (String str : arr) {
	  if (!cache.add(str)) {
		cache.remove(str);
	  }
	}
	
	for (String str : arr) {
	  if (!cache.contains(str)) {
		return Optional.of(str);
	  }
	}
	
	return Optional.absent();
  }
  
  public static void main(String[] args) {
	String[] input = {"abc","def","klm", "lod", "lod", "abc","def","klm" , "abc","def","klm"};
	Optional<String> result = findEvenNumberExistedWord(input);
	print(result.get());
  }

How about an O(n) complexity with O(1) memory? Simple count the number of binary 1's in each number. For every count that has an even number of 1s and is greater than 0, output a 1.

public int evenInt(int[] a){
  int[] bitCount = new int[32];
  for(int numb : a){
    indexCount(numb, bitCount);
  }
  return computeEvenBits(bitCount);
}

private void indexCount(int numb, int[] bitCount){
  int pos = 0;
  while(numb != 0){
    bitCount[pos] += (numb & 1);
    numb = numb >> 1;
    pos++;
  }
}

private int computeEvenBits(int[] bitCount){
  int retVal = 0;
  for(int i = 31; i >= 0; i--){
    if(bitCount[i] > 0 && bitCount[i] % 2 == 0){
      retVal++;
    }
    retVal = retVal << 1;
  }
  return retVal;
}

I have two solutions for this:
Time O(nlogn) Space O(1) : Sort the number, traverse and keep track that a number appearing is appearing even or odd number of times. Sorting takes O(nlogn) while traversing is O(n).

Time O(N) Space O(#UniqueElementInArray)
Traverse the array XORing each element and inserting it in a hash table at the same time.
When we are done with the first traverse we will have XOR of all element in the array.
Now since XORing a number with itself is 0 we would be left with XOR of all the numbers that appeared odd number of times.
Now XOR this variable with all the keys present in the hash table, since hash table stored all the unique values it will nullify all the integers in XOR variable and would also insert XOR of any integer which is not present in initial XOR(Even integers).
After all this we would be left will XOR of all the integers having even occurrence, and since we only have one number with even occurrence we would have that number in XOR.

Example: int[] a = { 1, 1, 1, 2, 4, 4 };
xorVariable = 1^1^1^2^4^4 = (1^2);
xorVariable = xorVariable^1^2^4 ( from the hash table)
= 1^2^1^2^4 = 4.

A O( n ) Time and O ( 1 ) space solution. Uses xor. Assumption +ve numbers only. Not tested for negative numbers.

int findEven(int* a, int n)
{
	if (!a) return -1;
	int xor = a[0];
	for (int i = 1; i < n; i++)
	{
		xor ^= a[i];
	}

	for (int i = 0; i < n; i++)
	{
		if (a[i] & xor)
			continue;
		else
			return i;
	}

	return -1;

}

Make all of the odd occurrences even and all of the even occurrences odd by ignoring the first occurrence of each unique number. XOR all of the remaining numbers together. The remaining XOR value is the even number. O(n) time O(n) space.

Like this:

private static int findEven(final int[] array) {
  final HashSet<Integer> set = new HashSet<>();
  int output = 0;

  for(final int value: array) {
    if (set.contains(value)) {
      output ^= value;
    } else {
      set.add(value);
    }
  }
  return output;
}

package com.algo; 

public class EvenCount { 

public int eventCount(int[] a) { 
int output = 0; 
for (int i = 0; i < a.length; i++) { 
output = output ^ a[i]; 
} 
return output; 
} 

public static void main(String[] args) { 

int[] a = { 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3 }; 
EvenCount count = new EvenCount(); 
System.out.println(count.eventCount(a)); 

} 
}