CareerCup

1. XOR all the n numbers.
2. Result will be knocked out for all the even pairs as a^a=0 The result now contains only XOR of the two odd out numbers.
3. Find the first bit position in the result that is 1. Definitely this bit position both the odd numbers have different bit values. i.e. one has a 0 and another has a 1 at this position. Let this position be x
4. XOR the elements that have 1 at x bit position and XOR the elements that have 0 at x bit position. The two XOR results would give the two odd count numbers.

Simpler solution at the cost of space:

- Create a hash set
- Loop the integers
-- If the element is in the hash set, remove it
-- Otherwise, add it (since it's not already present)
- The answer is the contents of the hash set (which scales to any number of odd numbers)

Complexity: O(n) (due to an O(1) get/put hash set).

Next code in javascript returns array of two needed numbers (8,4)

var inn=[1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,9,1,2,3,4,1,2,3];
var out = {};
for(var i=0; i<inn.length; i++)    {
	if(out[inn[i]]==null)
	   out[inn[i]]=inn[i];
    else
        delete(out[inn[i]]);
    }

public List<Integer> findNumbers(int[] a) {
		List<Integer> list = new ArrayList<Integer>();
		
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		
		for(int i=0; i<a.length; i++) {
			Integer key = new Integer(a[i]);
			if (map.containsKey(key)){
				Integer count = new Integer(map.get(key).intValue() + 1);
				map.put(key, count);
			} else {
				map.put(new Integer(a[i]), new Integer(1));
			}
		}
		
		for(Integer key: map.keySet()) {
			Integer value = map.get(key);
			if (value.intValue()%2 != 0) {
				list.add(key);
			}
		}
		
		return list;
		
	}

How would you solve this in JAVA?

My java solution in O(n):

import java.util.*;

public class Array_Odd_Occ {
	public static void main(String[] args) {
		int a[]={2,3,2,3,3,4,5,4,2,2,5,6};
		findNumbers(a);
	}
	
	private static void findNumbers(int [] a) {
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		
		for (int i = 0; i < a.length; i++) {
			Integer freq = map.get(a[i]);
			map.put(a[i], (freq == null) ? 1 : freq + 1);
		}
		
		for(Map.Entry<Integer, Integer> nums : map.entrySet()) {
			if(nums.getValue() % 2 != 0)
				System.out.println(nums.getKey());
		}
	}
}

Output:

3 6

private static void find_odd_repeating_numbers(int[] array) 
	{
		Map<Integer, Integer> nums = new HashMap<Integer, Integer>();
		for(int i : array)
		{
			if(nums.containsKey(i))
				nums.remove(i);
			else
				nums.put(i, 0);	
		}
		System.out.println(nums);
	}

1. XOR all the numbers to get c = a^b
2. reiterate the array and get d = c^arr[i] & e = c^arr[i]'
if (d = e')
arr[i] is one number
use the concept:
d = (a^b)^a = b
e = (a^b)^a' = b'

package linearData;

import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Set;

public class OddOneOut {
	public static void main(String[] args) {
		int a[] = {1,2,3,4,2,1,3,6,6,6};
		int length = a.length;
		HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
		
		for(int i = 0; i < length; i++ )
		{
			if(hm==null)
			{
				hm.put(1, a[i]);
			}
			else
			{
				if(hm.containsKey(a[i]))
				{
					int val = hm.get(a[i]);
					val++;
					hm.put(a[i], val);
				}
				else
					hm.put(a[i], 1);
			}
		}
		
		Set s = hm.entrySet();
		//Map<T, E> map 
		for (Entry<Integer, Integer> entry : hm.entrySet()) {
	         if (entry.getValue()%2!=0) {
	        	 System.out.println(entry.getKey());
	         }
	     }

	}
}

#You are given an integer array, where all numbers except for
#TWO numbers appear even number of times. 
#Q: Find out the two numbers which appear odd number of times.

intarr = [1,2,3,4,5,6,7,8,9,10,1,2,4,5,6,7,8,9]


def find_two_ints_not_even(intlist):
    odd_int={}
    retlist=[]
    for _int in intlist:
        if _int in odd_int:
            odd_int[_int]=odd_int[_int]+1
        else:
            odd_int[_int]=1
    for val1 in odd_int:
        if odd_int[val1] % 2 == 1:
            retlist.append(val1)
        if len(retlist)==2:
            return retlist
    return retlist

print find_two_ints_not_even(intarr)

I had hard time understanding the solution(s) mentioned here. So if you guys are facing the same problem here is the link for better understanding. Upvote so everybody can see.
geeksforgeeks.org/find-the-two-numbers-with-odd-occurences-in-an-unsorted-array/

Simple solution in python!

def findOddElement(arr):
	D = [] 								#final list of items that will be returned
	for item in arr:
		if arr.count(item) % 2 != 0: 	#check if odd
			if D.count(item) != 0: 		#value was already added to list
				D.append(item)
	return D

List<Integer> list = new ArrayList();
	for(int num: arr){
		if(list.contains(num){
			list.remove(num);
		}
		else{
			list.add(num);
		}
	}
	System.out.println(list);

Keep a hashmap with the integers as keys. Delete repeats (evens). O(n) time, but uses additional space, up to about almost n. There could be a lot of unique (1-count) entries.

function findOddAppearances(list) {
	var numMap = {};

	list.forEach(function(num) {
		if (numMap[num]) {
			delete numMap[num];
		} else {
			numMap[num] = true;
		}
	});

	return Object.keys(numMap);
}

var input = [0,0, 1,1, 2,2,2, 3,3, 4,4,4,4, 5,5,5, 6,6];

console.log(findOddAppearances(input)); // => [2,5];

How does this logic works?I mean what is the logic with finding first bit with 1 not the second, not the 3rd ?

a = [2,3,2,3,3,4,5,4,2,2,5,6]
res = []
for v in a:
    if a.count(v) %2 != 0:
        res.append(v)

print(set(res))

using Javascript object

var array = [2, 3, 2, 3, 3, 4, 5, 4, 2, 2, 5, 6];
var count = {};
var result = {};
array.forEach(item => {
  if (count[item]) {
    count[item] = count[item] + 1;
  } else {
    count[item] = 1;
  }
  if (count[item] % 2 !== 0) {
    result[item] = count[item];
  } else {
    delete result[item];
  }
});

Time Complexity: O(n)

1. XOR all the n numbers.
2. Result will be knocked out for all the even pairs as a^a=0 The result now contains only XOR of the two odd out numbers.
3. Find the first bit position in the result that is 1. Definitely this bit position both the odd numbers have different bit values. i.e. one has a 0 and another has a 1 at this position. Let this position be x
4. XOR the elements that have 1 at x bit position and XOR the elements that have 0 at x bit position. The two XOR results would give the two odd count numbers.

last line of algorithm does not lead to result...so problem is, how could we find two numbers by knowing their XOR.

Good Answer.