How to find all odd occurring elements in an array in Java

Question

I am trying to find all the elements which occur an odd number of times in an array. I worked out a little bit, but my code is only returning the correct answer if there is only one number which occurs odd number of times. If there are two or more odd occurring numbers than I am not able to process it. What I understand is that if we do bit-wise XOR of elements than we get one odd occurring element. How can I improve it for multiple numbers?

Below is my code:

public class OddOccur {
    public int oddoccurence(int[] arr, int size) {
        int res = 0;
        int[] fin = new int[size];

        for (int i = 0; i < size; i++) {
            res = res ^ arr[i];

        }
        return res;
    }

    public static void main(String args[]) {
        int[] arr = { 2, 5, 5, 2, 2, 3, 3, 3 };

        int n = arr.length;
        OddOccur obj = new OddOccur();

        System.out.println("odd occuring element is:"
                + obj.oddoccurence(arr, n));
    }
}

Need help to solve this issue!

Answer 1

public int oddoccurence(int[] arr, int size);

First, there can be multiple numbers that occur an odd number of times. There's no way to write this function and make it work if it only returns a single int. You'll need a function which can return multiple numbers.

public int[] oddOccurrences(int[] array);

Second, don't try to be clever. Using XOR is "clever". You're not going to find a simple solution using XOR. It'll be some convoluted, complicated mess. Keep it simple:

1. Count the number of times each number appears.
2. Then find all the odd counts.

Example pseudo-code:

// Map from numbers to counts. Assume the counts start at 0.
Map<Integer, Integer> counts;

for (number in array) {
    counts[number] += 1
}

// List of numbers that occur an odd number of items.
List<Integer> oddNumbers;

for (number, count in counts) {
    if (count % 2 != 0) {
        oddNumbers.add(number);
    }
}

Answer 2

Maybe an old post.. but here my answer.

In my opinion is not necessary to count the occurrences of a number to determine if it's odd or not. Let's use a data structure like a Set and just add to it the item if is still not prenent or remove it if already there.

Something like this:

public int solution(int[] A){

    Set<Integer> unpaired = new HashSet<Integer>();
    for (int i = 0; i<A.length; i++){
        if (unpaired.contains(A[i])){
            unpaired.remove(new Integer(A[i]));
        }else{
            unpaired.add(A[i]);
        }
    }


    // all printed out values are odd
    for (Integer res : unpaired){
        System.out.println(res);
    } 
}

Answer 3

This solution scored 100% on codility. What we do is simply initialize a HashMap. The lookup time for a HashMap is O(1) constant time, see here for more info. Since we loop through the entire array only once, we end up with O(N) time, where N is the length of the array.

If an element already exists in the HashMap, then we can remove it since we have found its corresponding pair. By the end of this, we should end up with a HashMap with only a single pair. Simply output this number and you are done.

import java.util.*;
class Solution {
    public int solution(int[] A) {
        int key;
        Map<Integer, Integer> unpaired = new HashMap<Integer, Integer>();
        for (int i = 0; i < A.length; i++){
            key  = A[i];
            Integer value = unpaired.get(key);
            if (value != null){
                unpaired.remove(key); // Remove by key
            }
            else{
                unpaired.put(key,0);
            }
        }
        for (Map.Entry<Integer, Integer> entry : unpaired.entrySet())
        {
            key =  entry.getKey();
        }
        return key;
    }
}

Answer 4

This score 100 % .

public int solution(int[] A) {
    Arrays.sort(A);
    for(int i = 0; i < A.length; i = i+2){
        if(i == A.length-1)
        return A[i];

        if (A[i]!=A[i+1])
        return A[i];
    }
    return 0;
}

Answer 5

You don't really need to keep track of how many times you've seen each integer, only whether you've seen it an odd number of times. So start with your data structure (map, hash table, dictionary, whatever) being empty, which correctly reflects the state that you have seen no numbers an odd number of times. Now for each number x in the array, if x is in the map then remove it (now you've seen it an even number of times) otherwise add it

Answer 6

Here is my solution using HashMap:

 public int solution(int[] A) {

        HashMap<Integer, Integer> map = new HashMap<>();
        HashSet<Integer> val = new HashSet<>();
        for (int i=0; i<A.length; i++){
        if (map.get(A[i]) == null) {
            map.put(A[i], 1);
        } else map.put(A[i], map.get(A[i])+1);

        if (map.get(A[i])%2 == 1) 
            val.add(A[i]);
            else val.remove(A[i]);
        }

        Iterator<Integer> itr = val.iterator();  
        return itr.next();  

    }

Answer 7

I think use a Map to store the number of occurrences is the right method to solve this problem，but if the different numbers is too many it need more memory，use BitMap can also realize and need less memory.

public static List<Integer> oddNumbers(int[] array, int size) {
        BitSet bitSet = new BitSet();
        for (int i = 0; i < size; i++) {
            bitSet.flip(array[i]);
        }

        List<Integer> resp = new ArrayList<>();
        for (int i = 0; i < bitSet.length(); i++) {
            if (bitSet.get(i)) {
                resp.add(i);
            }
        }
        return resp;
    }

The test case is:

@Test
public void test_oddNumbers() throws Exception {
    int[] arr = {2, 5, 5, 2, 2, 3, 3, 3, 1, 7, 8, 9, 9, 9};
    List<Integer> resp = oddNumbers(arr, arr.length);
    assertTrue(resp.size() == 6);
    assertTrue(resp.containsAll(Arrays.asList(1, 2, 3, 7, 8, 9)));
}

Answer 8

//This solution scored 100% on codility.

import java.util.Arrays;

class Solution {

public int solution(int[] A) {
    // write your code in Java SE 8

    Arrays.sort(A);

    int length = A.length;

    for (int i = 0, j = 1; i < length; i++) {
        if (j < length && A[i] == A[j]) {
            i++;
            j = j + 2;
        } else {
            return A[i];
        }
    }

    return 0;   
}

}

Answer 9

The problem is pretty simple, just use bitwise xor on all the elements of the array. The reason is that only one element is unpaired.

Answer 10

 private static int Odd(int[] a) {
        int unpaired;
        unpaired = a[0];

        for(int i = 1; i< a.length; i++){
            unpaired = unpaired ^ a[i]; // xor
        }

        return unpaired;
    }

Answer 11

Program in kotlin

fun oddOccurrencesInArray(array: IntArray) {
   
    var count = 0
    var arrayList = mutableListOf<Int>()
    array.sort() //sort the array
    var element = array[0]
    for (j in 1 until array.size) {
        if (element == array[j]) {
            count++
        } else {
            if (count == 0)
                arrayList.add(array[j-1])
            count = 0
            element=array[j]
        }
    }
    if(count==0)
        arrayList.add(array[array.size-1])
    println("Given array: ${array.contentToString()} missing:${arrayList.toString()}")
}

Answer 12

This scored 100% in Codility using a Set object and simply adding if !exist or removing if exists.

public int solution(int[] A) 
{
    Set<Integer> oddSet = new HashSet<>();
    
    for(int i = 0; i < A.length; i++)
    {
        if(!oddSet.contains(A[i]))
        {
            oddSet.add(A[i]);
        }
        else
        {
            oddSet.remove(A[i]);
        }
    }
    /* Based on the pre-conditions, we are sure that only one 
       remains here that is unique. So we just return that. */
    return oddSet.iterator().next();
}

Answer 13

100% solution in C# using Linq. It's nice to see that Linq is fast enough.

  public static int solutionOddOccurrencesInArrayLinq(int[] A)
    {
        if (A.Length == 0)
            return 0;

         var result = A
            .GroupBy(e => e)
            .Where(g => g.Count() % 2 == 1)
            .Select(g => g.Key);

        return result.FirstOrDefault();

    }

Answer 14

This solution gave me 100% pass on codility:

  public int solution(int[] A) {

        if (A.length == 0) {
            return 0;
        }
        int num = 0;
        for (int i = 0; i < A.length ; i++) {
            // using XOR function 1. XOR of number with itself = 1 and XOR number with 0 = number itself
            num = num ^ A[i];
        }


        return num;
    }

Answer 15

public class GetOddOccurenceInArray {
    
    public static ArrayList<Integer> getOddOccurence(int arr[]){
        
        int count = 0;
        ArrayList<Integer> result = new ArrayList<>(); 
        HashMap<Integer, Integer> hmap = new HashMap();

        for(int num : arr){
            if(hmap.get(num) == null){
                hmap.put(num, count+1); 
            }
            else
                hmap.put(num, hmap.get(num)+1);
        }
          
        for (Entry<Integer,Integer> entry : hmap.entrySet()) { 
            if(entry.getValue()%2==1){
                //System.out.println("number is "+entry.getKey());               
                result.add(entry.getKey());
            }

        }

        return result;      
    }
    
    public static void main(String[] args){
        int arr[] = {1,2,2,2,3,3,3,3,4,5,6,6,7,8};
        ArrayList<Integer> occurred = getOddOccurence(arr);
        System.out.println("numbers occurred odd times : "+ occurred.toString());   
    }
}