Given an array a[] of N positive integers, where elements are consecutive (sorted). Also, there is a single element which is repeating X (any variable) number of times. Now, the task is to find the element which is repeated.
while (start < end)
{
int mid = (start + end) / 2;
// if a[mid] >= mid + a[0], there is no repeating character in [start,mid]
if (a[mid] >= mid + a[0])
start = mid + 1;
// if a[mid] < mid + a[0], there is a repeating character in [start,mid]
else
end = mid;
}
Aucun commentaire:
Enregistrer un commentaire