Odd Occurring Number in Array

It is Sunday again, seems like last week came and went by faster than usual.

When I browse YouTube videos on my phone, I tend to run into some that I would like to watch and if possible experiment with the subject. This post is associated with a video by Irfan Baqui. It is nice to get a challenge, understand what it is required, solve it and see how a fellow developer comes to the same solution using a different and in some cases the same approach.

I would like to note, that when you solve a challenge on HackerRank or LeetCode, you must choose a programming language. Your solution needs to compile, run and pass a set of tests and in some cases it is ranked for performance. It seems that Irfan does not produce code; it leaves the challenges in the pseudo code stage.

The description for this challenge follows:

You are given an array of repeating numbers. All numbers repeat in an even way, except for ONE. Find that occurring number.

I solved this simple challenge using Java. The test code follows:

	/*
	 * 
	 */
	public static void main(String[] args) {

		final int arr[] = {1, 4, 6, 4, 1, 7, 4, 6, 4};
//		final int arr[] = {};
//		final int arr[] = {1, 2, 3};
//		final int arr[] = {2, 2};

	System.out.println(oddNumber(arr));
	}

The output from the Eclipse IDE console follows:

7

As one can tell by the different arrays that I tested, the only one that should work is the first. The result is number 7. Number 4 is found four times in this example.

The actual code follows:

package canessa.odd.number;

import java.util.HashMap;

/*
 * You are given an array of repeating numbers. All
 * numbers repeat in an even way, except for ONE.
 * Find that occurring number.
 */
public class Solution {

	/*
	 * For simplicity this function returns -1 in case of errors,
	 * or it could throw an exception.
	 */
	static int oddNumber(int[] arr) {
		
		HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
		
		// **** sanity check ****
		if ((arr.length % 2) == 0) {
//			System.err.println("UNEXPECTED arr.length: " + arr.length);
//			return -1;
			throw new IllegalArgumentException("UNEXPECTED arr.length: " + arr.length);
		}
		
		// **** traverse array (only odd number should remain) ****
		for (int val : arr) {
			if (hm.containsKey(val)) {
				hm.remove(val);
			} else {
				hm.put(val, val);
			}
		}
		
		// **** should not happen ****
		if (hm.size() != 1) {
//			System.err.println("UNEXPECTED hm.size: " + hm.size());
//			return -1;
			throw new IllegalArgumentException("UNEXPECTED hm.size: " + hm.size());
		}
		
		// **** return odd value ****
		return (int) hm.values().toArray()[0];
	}
	
	/*
	 * 
	 */
	public static void main(String[] args) {

		final int arr[] = {1, 4, 6, 4, 1, 7, 4, 6, 4};
//		final int arr[] = {};
//		final int arr[] = {1, 2, 3};
//		final int arr[] = {2, 2};

	System.out.println(oddNumber(arr));
	}

}

Please note that I went overboard by adding code to throw and check for exceptions. The reason is that when I experiment with something, I tend to encounter options and in some cases, like to pursue ideas. For example, I checked different ways on how to return the odd value by the method. In general, there are different ways to implement most code, but only one seems to be best. When working with production code, as soon as the code is operational and tested, it is not a bad idea to see if it can be optimized or refactored to make it easier to understand and maintain. In most cases, faster code is always welcomed.

If you have comments or questions, please leave me a note at the end of this post. I will address it as soon as possible.

Happy software development;

John

Follow me on Twitter:  @john_canessa

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.