CODEWITHSUNDEEP
javaalgorithm
FLY FOX 2058
FLY FOX 2058

Reputation: 13

Algorithms task about finding not unique number in array

I'm new at algorithms and want to know how to solve this task. A detailed Java solution is desirable.

You have been given an integer n≥2 and an integer array A[0..n−1] which is sorted in nondecreasing order . All numbers repeat 1 time but one number repeats 2 times, how do you find the number that repeat 2 times. Using data structures and built-in functions was not allowed. Complexity of algorithm should be O(lg(n))

Upvotes: 1

Views: 51

Answers (1)

trincot
trincot

Reputation: 350147

You can use a custom binary search algorithm.

We can observe that if there would be only values that repeated once (which occur twice), then the size of the array is even, and we have for each even index i: A[i] == A[i+1].

Since there is exactly one triplet, the array's size is odd, and so if we find an even index i for which A[i] == A[i+1] we know that the triplet did not occur at the left side of i. If however A[i] != A[i+1], then we are sure the triplet occurred at the left side of i.

This is all we need to perform a binary search. We should just make sure we always make our checks at even indices.

Here is an implementation in JavaScript:

function binarySearchTriplet(arr) {
    let lo = 0, hi = arr.length - 1; // even
    while (lo < hi) {
        // Take mid, but force it to be even
        mid = (lo + hi) >> 2 << 1;
        if (arr[mid] === arr[mid+1]) {
            lo = mid + 2;
        } else {
            hi = mid;
        }
    }
    return arr[lo];
}

let arr = [1,1,4,4,4,5,5,7,7,2,2,6,6,8,8];
console.log(binarySearchTriplet(arr)); // 4

Upvotes: 3

Related Questions