CC-19 : Find first non repeating number.

Description:

Given a sorted input array where each element is repeated twice, except for 1 non repeating element. Find and return the non-repeating element.

Test cases and expected outputs:

Input Parameters	Expected outputs
Array1: 33, 33, 67, 67, 96, 122, 122, 201, 201,	First Non repeating number is 96
Array2: 33, 33, 67, 67, 96, 96, 122, 122, 201,	First Non repeating number is 201

Pseudocode:

findNonRepeatingNumber (nums[]):

Integer array named nums is received as input parameters.

Set integer variable firstIdx to zero, we will use this variable to check the first index of partition in which are searching for required integer.

Set integer variable lastIdx to nums.length-2, we will use this variable to check the last index of partition in which are searching for required integer.

If nums.length==1, return nums[0] as array has only one element.

If (nums[nums.length-1] !=nums[nums.length-20) return nums[nums.length-1] as last number of array is non repeating.

Set integer variable insIdx to -1, we will use this variable to store the position at which toSearch can be inserted in nums.

While (firstIdx <= lastIdx) do the following steps:

Set integer variable midIdx to (lastIdx+firstIdx)/2.

If (nums[midIdx]!=nums[midIdx+1) and mums[midIdx] !=nums[midIdx+1]:

Return nums[midIdx]asit is the reuired non repeating number.

Else if (midIdx%2==1) and (nums[midIdx]==nums[midIdx-1]) OR if (midIdx%2==0) and (nums[midIdx]==nums[midIdx+1]) then:

Set firstIdx=midIdx+1, as we need to search in the higher partition now.

Else:

Set lastIdx=(midIdx-1) as we need to search in lower partition now.

If non repeating element is not found above, return -1.

Code:

public int findNonRepeatingNumber(int[] nums){
	int firstIdx=1;
	int lastIdx=nums.length-2;
	if (nums.length==1) {return nums[0];}
	if (nums[0] != nums[1]) {return nums[0];}
	if (nums[nums.length-1] != nums[nums.length-2]) {return nums[nums.length-1];}
	while (firstIdx <= lastIdx) {
		int midIdx=(lastIdx+firstIdx)/2;
		if ((!(nums[midIdx]==nums[midIdx+1])) && (!(nums[midIdx]==nums[midIdx-1]))) {
			return nums[midIdx];
		} 
		
		if (((midIdx%2==1)&& (nums[midIdx]==nums[midIdx-1])) ||
		((midIdx%2==0)&& (nums[midIdx]==nums[midIdx+1]))){
			firstIdx=midIdx+1;
		}else{
			lastIdx=midIdx-1;
		}
	}	
	return -1;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class SearchNonRepeatingNumber {

public int findNonRepeatingNumber(int[] nums){
	int firstIdx=1;
	int lastIdx=nums.length-2;
	if (nums.length==1) {return nums[0];}
	if (nums[0] != nums[1]) {return nums[0];}
	if (nums[nums.length-1] != nums[nums.length-2]) {return nums[nums.length-1];}
	while (firstIdx <= lastIdx) {
		int midIdx=(lastIdx+firstIdx)/2;
		if ((!(nums[midIdx]==nums[midIdx+1])) && (!(nums[midIdx]==nums[midIdx-1]))) {
			return nums[midIdx];
		} 
		
		if (((midIdx%2==1)&& (nums[midIdx]==nums[midIdx-1])) ||
		((midIdx%2==0)&& (nums[midIdx]==nums[midIdx+1]))){
			firstIdx=midIdx+1;
		}else{
			lastIdx=midIdx-1;
		}
	}	
	return -1;
}

public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	int retVal;
	try {
	
	SearchNonRepeatingNumber search=new SearchNonRepeatingNumber();
	int[] nums= { 33,33,67,67,96,122, 122, 201,201};
	
	
	System.out.println("\nArray1:");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < nums.length; arrayIndex++) {
		System.out.print(nums[arrayIndex]+", ");		
	} 
	retVal=search.findNonRepeatingNumber(nums);
	System.out.println("\n\nNon repeating number is "+ retVal);	
	
	int[] nums1= { 33,33,67,67,96,96,122, 122, 201};
	System.out.println("\nArray2:");
	arrayIndex=0;
	for (arrayIndex=0; arrayIndex < nums1.length; arrayIndex++) {
		System.out.print(nums1[arrayIndex]+", ");		
	}
	retVal=search.findNonRepeatingNumber(nums1);
	System.out.println("\n\nNon repeating number is "+ retVal);	
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}

}