## Interview Question

Country: United States

Comment hidden because of low score. Click to expand.
5
of 5 vote

Step 1:Divide the array in 2 parts such that the first part contains even number of elements.
Step 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.

Comment hidden because of low score. Click to expand.
-2

what if the array is 0,0,1,1,4,4,4,4,5 your algo wont work

Comment hidden because of low score. Click to expand.
2

Question says that all the numbers just occur twice and only number occurs once. So the input which you are stating is invalid :)

Comment hidden because of low score. Click to expand.
2
of 2 vote

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];

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

{
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;
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}

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);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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));
}``````

Comment hidden because of low score. Click to expand.
0

Sorry, m = middle. Also, need to handle case where m is zero.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

XOR on all numbers ... The result will be the number that appears only once.

Comment hidden because of low score. Click to expand.
1
of 1 vote

I would assume this would be O(n) since you need to visit every number.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.