FactSet Interview Question
If you have a sorted array that is initialized with size 100, the values stored would be for example 1, 2, 3,.... ect. Describe an algorithm that would check if there is a duplicate number and if so return it.
Interview Answers
this seems not using the sorted condition, there can be better solution
This is a sorted array. So the duplicates, if present must be side by side. We can use XOR operation to find this.
public class DuplicateElementInArray {
public static int checkDup(int array[]) {
for(int i=0; i
if the values are 1..100 with one of them repeated, add them up and subtract sigma(1,100) = O(n)
Perform binary search where A[mid] == A[mid-1] || A[mid]==A[mid+1] with care for Array index bounds. This will be done in log n