## 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.