Today I thought I would take a look at a small interview question with a small gimmick:
In an unsorted array of numbers that occurs an even number of times except one that occurs an odd number of times, find the number that occurs an even number of times.
Turns out we can do the usual Sorting and Hash Table with the usual complexity explained and then our last solution uses one property that only numbers occurring twice have. XORing a number with itself an even number of times will result in a 0!
How To Find the Only Int Occurring an Even Number of Times in an Array – Sorting
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
/* * @Author: Ajk Palikuqi * * @Question: How To Find the Only Int Occurring an Even Number of Times in an Array */ package iqLib.arrayLib; import java.util.HashMap; import java.util.Iterator; import java.util.Map; import java.util.Map.Entry; import iqLib.sortLib.QuickSort; public class OddBetweenEvens { public static int FindOddBetwenEvensBySorting(int[] numbers) throws Exception { int length = numbers.length; QuickSort.Sort(numbers); int currentNum = numbers[0]; int currentNumOccurences = 1; for (int i = 1; i < length; ++i) { if (numbers[i] != currentNum) { if (currentNumOccurences % 2 == 1) { return currentNum; } currentNum = numbers[i]; } } throw(new Exception()); //Checked exception in Java } } |
How To Find the Only Int Occurring an Even Number of Times in an Array – Hashing
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
/* * @Author: Ajk Palikuqi * * @Question: How To Find the Only Int Occurring an Even Number of Times in an Array */ package iqLib.arrayLib; import java.util.HashMap; //Simple Hash Table in Java import java.util.Iterator; import java.util.Map; import java.util.Map.Entry; import iqLib.sortLib.QuickSort; public class OddBetweenEvens { public static int FindOddBetweenEvensByHashing(int[] numbers) throws Exception { //Make a HashMap - Integer -> Integer, which points each number to it's count. Map<Integer, Integer> numbersCount = new HashMap<Integer, Integer>(); int length = numbers.length; for (int i = 0; i < length; ++i) { int currentCount = 0; if (numbersCount.containsKey(numbers[i])) { currentCount += numbersCount.get(numbers[i]); } numbersCount.put(new Integer(numbers[i]), new Integer(currentCount)); } Iterator<Entry<Integer, Integer>> it = numbersCount.entrySet().iterator(); int oddNumbersCount = 0; int oddNumber = 0; while(it.hasNext()) { Map.Entry<Integer, Integer> pair = (Map.Entry<Integer, Integer>)it.next(); if (pair.getValue() % 2 == 1) { oddNumbersCount++; oddNumber = pair.getKey(); } } if (oddNumbersCount == 1) { return oddNumber; } throw(new Exception()); } } |
How To Find the Only Int Occurring an Even Number of Times in an Array – XOR
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
/* * @Author: Ajk Palikuqi * * @Question: How To Find the Only Int Occurring an Even Number of Times in an Array */ package iqLib.arrayLib; import iqLib.sortLib.QuickSort; public class OddBetweenEvens { public static int FindOddBetweenEvensGoodPerformance(int[] numbers) { int length = numbers.length; int result = 0; for (int i = 0; i < length; ++i) { result ^= numbers[i]; } return result; } } |
Food for thought: What happens if 0 appears an odd number of times?
Hope you guys enjoyed it… and I’ll see you guys next time ;D
The following two tabs change content below.
If you like one of my posts the best way to support is give it a thumbs up, comment, or share it on social media 🙂
Latest posts by Ajk (see all)
- Find Median from Numbers Array - January 1, 2018
- Find Whether a Number Can Be the Sum of Two Squares - August 12, 2017
- How to Find Two Primes Whose Sum is Equal to a Number N - April 22, 2017