Deepak Tiwari - 4 months ago 38

Java Question

I had an interview and there was a question. Find unique numbers from sorted array in less than O(n) time.

`Ex: 1 1 1 5 5 5 9 10 10`

o/p 1 5 9 10

I gave the solution but that was of O(n). Can anyone help me with this thread.

Answer

**Divide and conquer**:

- look at the first and last element of a sorted sequence (the initial sequence is
`data[0]..data[data.length-1]`

). - If both are equal, the only element in the sequence is the first (no matter how long the sequence is).
- If the are different, divide the sequence and repeat for each subsequence.

Solves in **O(log(n))** in the average case, and O(n) only in the worst case (when each element is different).

Java code:

```
public static List<Integer> findUniqueNumbers(int[] data) {
List<Integer> result = new LinkedList<Integer>();
findUniqueNumbers(data, 0, data.length - 1, result, false);
return result;
}
private static void findUniqueNumbers(int[] data, int i1, int i2, List<Integer> result, boolean skipFirst) {
int a = data[i1];
int b = data[i2];
// homogenous sequence a...a
if (a == b) {
if (!skipFirst) {
result.add(a);
}
}
else {
//divide & conquer
int i3 = (i1 + i2) / 2;
findUniqueNumbers(data, i1, i3, result, skipFirst);
findUniqueNumbers(data, i3 + 1, i2, result, data[i3] == data[i3 + 1]);
}
}
```