CODEWITHSUNDEEP
arraysalgorithmsortinghashtable
Jake
Jake

Reputation: 16857

Repeated number in sorted array

I was asked this question recently in an interview :

What is the most efficient way to find a repeated number in a sorted array?

My answer was based on using a hash table with key as array element and number of repetitions in array as value; iterate the array and update hash table. In the end, hash table can be checked for elements with count > 1 ; those are the repeated elements.

Is there a better way to do this ?

Thanks.

Upvotes: 2

Views: 1695

Answers (4)

Kunal Gaurav
Kunal Gaurav

Reputation: 1

public static int searchrepeativeVal(int a[]){

    int left =0;
    int right= a.length;
    int mid;

    while (right-left>1){

        mid= (left+right)/2;

        if(a[mid]!=mid+1){
            if(a[mid]== mid){
                return mid;
            }else{
                right=mid;
            }
        }else{

            if(a[mid]==mid ){
                return mid;
            }else{
                left =mid;
            }
        }
    }

    return -1;
}

Upvotes: -1

jdl
jdl

Reputation: 6323

-Sort the Array

-find the difference between adjacent indices values

-if the difference is 0 then there is a repeat and note the indices

Upvotes: 0

Óscar López
Óscar López

Reputation: 236112

Check every element in the array (except the last one) with the next element, if they're equal then stop and exit: you've found a repeated element. It works because the array is sorted, it doesn't require any additional space and in the worst case (no repeated elements) it'll be O(n), because all of the array will have to be traversed.

Upvotes: 2

noMAD
noMAD

Reputation: 7844

Well, you can do this with space of O(1). Since its a sorted array, all you need to do it to subtract the current number with the next one. If the result is 0 then you have a repeated number.

Upvotes: 3

Related Questions