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**