OddOccurrencesInArray

Solution

This java solution to codility problem OddOccurrencesInArray scored 100%

Logic: Iterate over the elements, one by one, add the element to a set only if it does not exist in the set, if it exists then remove the element. At the end of the iteration only the unpaired element will remain in the set and that is what you return. Can you make this better?

import java.util.HashSet;
import java.util.Set;

//Detected time complexity:
//O(N) or O(N*log(N))
public class OddOccurrencesInArray {

    public int solution(int[] A) {
        Set<Integer> values = new HashSet<>();
        for (int i = 0; i<A.length; i++) {
            if (values.contains(A[i])) {
                values.remove(A[i]);
            } else {
                values.add(A[i]);
            }
        }
        return values.iterator().next();
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s