Interview Question
Country: United States
n is odd.
first look at the element A[n/2+1].
if A[n/2 +1] == A[n/2]
search the left part (from 0 to n/2-1) //the number of the left part is odd, so it's where the target is.
else if A[n/2+1] == A[n/2+2]
search the right part (from n/2+3, n-1)// the number of the right part is odd, so it's where the target is
else
return A[n/2];
Problem solving process:
- You see "sorted array"
- You see lg(n)
Above suggest you try some modified binary search.
Then on paper you work with examples (check middle elements) and decide two things:
1) For this specific problem, which half would I choose and how would I choose it
2) What is the ending condition
{
public class OccurringOnce {
public static void main(String[] args) {
// int[] arr = { 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7 };
// int[] arr = { 0, 0 ,1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7 };
// int[] arr = { 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 7 };
// int[] arr = { 0, 0, 1, 1, 2, 2 };
int[] arr = { 1, 1, 3 };
System.out.println(findNumber(arr, 0, arr.length - 1));
}
private static int findNumber(int[] arr, int start, int end) {
int mid = (start + end) / 2;
// handling case when length of array is even number
if (arr.length % 2 == 0) {
return -1;
}
int num = -1;// return -1 if there is no occurrence of such element
if (mid - 1 >= start && arr[mid] == arr[mid - 1]) {
/*
* search element in right half of the array
*/
num = findNumber(arr, mid + 1, end);
} else if (mid + 1 <= end && arr[mid] == arr[mid + 1]) {
/*
* search element in left half of the array
*/
num = findNumber(arr, start, mid - 1);
} else {
/*
* return middle of the array
*/
num = arr[mid];
}
return num;
}
}
}
class BinaryOddAI
{
public static void Do()
{
int[] array = { 0, 0, 1, 2, 2 };
Console.WriteLine(GetOdd(array, 0, array.Length - 1));
int[] array2 = { 0, 0, 1, 1, 3, 2, 2 };
Console.WriteLine(GetOdd(array2, 0, array2.Length - 1));
int[] array3 = { 1, 1, 3 };
Console.WriteLine(GetOdd(array3, 0, array3.Length - 1));
}
private static int GetOdd(int[] array, int start, int end)
{
if (array == null || array.Length % 2 == 0)
{
return -1;
}
if (array.Length == 1)
{
return array[0];
}
if (start == end)
{
return array[start];
}
int mid = (start + end) / 2;
if (array[mid] != array[mid - 1] && array[mid] != array[mid + 1])
{
return array[mid];
}
if (array[mid] == array[mid + 1])
{
return GetOdd(array, start, mid - 1);
}
else
{
return GetOdd(array, mid + 1, end);
}
}
}
int FindSingle(A, i, j)
{
if (i == j) return -1;
int middle = (i + j) / 2;
if (A[m] != A[m - 1] && A[m] != A[m + 1]) return m;
return max(FindSingle(A, i, m - 1), FindSingle(A, m + 1, j));
}
Step 1:Divide the array in 2 parts such that the first part contains even number of elements.
- Stupid Developer October 20, 2013Step 2: Now compare the last element of first part to the first element of second part.
Step 3: If they match then the non-repeating element is in the first part of the array.
Step 4: Now make this is as your main array & go to step 1.