Single Element in a Sorted Array

Ventured into LeetCode and randomly selected the Single Element in a Sorted Array challenge. The requirements are very straight forward. Make sure you pay attention to the following Note: Your solution should run in O(log n) time and O(1) space.

Thought about the linear O(n) brute force approach. I did not bother playing with it given that it was not going to work. Doodle for a few minutes with the numbers and their indices in the array. The solution smelled like a binary search which requires a sorted array of elements.

The following screen capture is from the Eclipse IDE using sample data provided by the challenge and some that I made up:

1,1,2,3,3,4,4,8,8
3,3,7,7,10,11,11
1,1,9
1,8,8
3,3,9,9,10,13,13
1,1,8,10,10
1,1,2,2,8,10,10
-1

main <<< str ==>1,1,2,3,3,4,4,8,8<==
main <<< nums:  1  1  2  3  3  4  4  8  8 
                0  1  2  3  4  5  6  7  8 
2
main <<< str ==>3,3,7,7,10,11,11<==
main <<< nums:  3  3  7  7 10 11 11 
                0  1  2  3  4  5  6 
10
main <<< str ==>1,1,9<==
main <<< nums:  1  1  9 
                0  1  2 
9
main <<< str ==>1,8,8<==
main <<< nums:  1  8  8 
                0  1  2 
1
main <<< str ==>3,3,9,9,10,13,13<==
main <<< nums:  3  3  9  9 10 13 13 
                0  1  2  3  4  5  6 
10
main <<< str ==>1,1,8,10,10<==
main <<< nums:  1  1  8 10 10 
                0  1  2  3  4 
8
main <<< str ==>1,1,2,2,8,10,10<==
main <<< nums:  1  1  2  2  8 10 10 
                0  1  2  3  4  5  6 
8
main <<< str ==>-1<==

The sequence is terminated by a line with a -1. I display the values in the nums array separated by a space. The following line is the index in the nums array. The number left justified is the missing number.

My solution and test code written in Java 8 follows:

import java.util.Scanner;

public class Solution {

	/**
	 * Given a sorted array consisting of only integers where every element appears 
	 * twice except for one element which appears once. Find this single element 
	 * that appears only once.
	 */
	static int singleNonDuplicate(int[] nums) {
		int lo 	= 0;
		int hi 	= nums.length - 1;
		int mid	= 0;
		
		// **** ****
		
		while (lo <= hi) {
			mid = lo + (hi - lo) / 2;
			
			// **** ****
			
			if (lo == hi) {
				return nums[mid];
			}
			
			// **** ****
			
			if ((nums[mid - 1] != nums[mid]) &&
				(nums[mid] != nums[mid + 1])) {
				return nums[mid];
			}
			
			
			// **** ****
			
			if ((mid % 2) == 0) {		// even
				if (nums[mid] == nums[mid - 1]) {
					hi = mid + 1;		// go up
				} else {
					lo = mid - 1;		// go down
				}
			} else {					// odd
				if (nums[mid] == nums[mid - 1]) {
					lo = mid + 1;		// go up
				} else {
					hi = mid - 1;		// go down
				}
			}
		}

		// **** ****
		
		return -1;
	}

	/**
	 * Test code.
	 */
	public static void main(String[] args) {
	
		// ***** open scanner ****
		
		Scanner sc = new Scanner(System.in);
	
		// **** loop until told to exit ****
		
		Boolean done = false;
		while (!done) {
		
			// **** ****
			
			String str = sc.nextLine();
			System.out.println("main <<< str ==>" + str + "<==");
			
			// **** check if we are done ****
			
			if (str.equals("-1")) {
				done = true;
				continue;
			}
			
			// **** build array of integers ****
			
			String ints[] = str.split(",");
			int[] nums = new int[ints.length];
			System.out.print("main <<< nums: ");
			for (int i = 0; i < ints.length; i++) {
				nums[i] = Integer.parseInt(ints[i]);
				System.out.printf("%2d ", nums[i]);
			}
			System.out.println();
			System.out.print("               ");
			for (int i = 0; i < ints.length; i++) {
				System.out.printf("%2d ", i);
			}
			System.out.println();
			
			// **** call method ****
			
			System.out.println(singleNonDuplicate(nums));
		}
		
		// **** close scanner ****
		
		sc.close();

	}

}

If you have comments or questions regarding this or any other post in this blog, please do not hesitate and send me a message. Will reply as soon as possible and will not use your name unless you explicitly allow me to do so.

Enjoy;

John

john.canessa@gmail.com

Follow me on Twitter:  @john_canessa