6.3k views

The minimum number of comparisons required to determine if an integer appears more than $\frac{n}{2}$ times in a sorted array of $n$ integers is

1. $\Theta(n)$

2. $\Theta(\log n)$

3. $\Theta(\log^*n)$

4. $\Theta(1)$

+23
Find the first index ,say $i$ and last index , say $j$ of the element in array using using binary Search in $O(log(n))$ time and then $j-i+1$ is equal to the occurence of the element in array.

Now check if it is greater than $n/2$ or not.
+1
this ques is purely based on how efficiently you read the question.
0

if array is if 1233346 , will log n complexity works?

0

@srestha

once we got the element which should have occurred more that n/2 times we count its total occurrences in O(logn) time.

this is what  given as the best answer

so in your example number 3 is found at n/2 and then we count its occurence which will take log n and then declare that it doesnt occure more than n/2

though how that count takes O(log n) is not clear to me

i think becasue it can be maximum upto n/2 times only so logn

0
We can proceed the algo like this....1st we have to check for the presence of the requested element in log n time ..then we have to chech in the either sides of that array index that we get in the first attemt to check whether that same element is present in either of the list or not...where either of those recursive cases it takes log n time each ...so time complexity required to check those sub arrays are log n + log n + log n.....so asymptotically it takes theta (log n) time...and here we can make use of static var which can counts the number of times we get the examined element in that array ...and finally we can compare that value with n/2 ...and if its value is more than that then we return 1 otherwise we return 0....

whenever there exists an element which is present in the array : more than $\frac{n}{2}$ times, then definitely it will be present at the middle index position; in addition to that it will also be present at anyone of the neighbourhood indices namely $i-1$ and $i+1$
No matter how we push that stream of More than $\frac{n}{2}$ times of elements of same value around the Sorted Array, it is bound to be present at the middle index $+$ atleast anyone of its neighbourhood

once we got the element which should have occurred more that $n/2$ times we count its total occurrences in $\mathcal{O}(\log n)$ time.

edited
+4
@Chhotu See first of all how to get the element that must have occurred more than n/2 times?
Tell me that.
Sol:: It takes O(lgn) time
0
Thanks for valuable reference and help. I was not thinking properly.
0
But sir we know that if a number has to present and occur more than n/2 it must have to present at middle position. And the given array is sorted so why we can't just directly go to the middle position and check for the number there and it's neighbor. In this way it should be O(1)
0

Let us take an ex -  1 1 2 2 3 3 3. So looking at 2 can we it is present n/2 times.  Look top comments you will get idea.

0

Chhotu  @Vs

Why are we searching for x in the middle position ?

As per question,If an integer appears more than n/2 times,so does this mean our function will take integer and check if it is occurring more than n/2. Or does this mean we need to check if there exists such integer?I interpreted as the former way but the answer assume as per later way.Please clear this

0
here binary search will be apply on both side of the middle element to count the >=(n/2) occurence

so time will be = 0(1) + 2(logn)           {0(1) for finding middle element}

=0(1) + 0(logn)

=0(logn)
0
Question is about minimum number of comparisons right? so why are we not considering 1st element it self for getting best results....means by checking occurrences of 1st element it will take only O(1) time...so ans should be O(1) ....
0
this give O(n) not O(logn)
0
In question they haven't asked the count of the number...so i think answer is constamt time...
0

What is the meaning of option (c) log* n ?

To check whether a given number is repeated n/2 times in the array can be done in O(log n) time.

Algo

1. find the first occurrence (index i) of x(given number) in the array which can be done in O(log n) time (a variant of binary search).

2. check if A[i] == A[n/2+i]

return true

3. else return false

How could you find first occurence in Logn time using a variant of BS?
+3
its An integer not The integer, so we should determine first what is the Integer $x$
The starting position of required element can be anywhere between

1 to n/2-1(inclusive).

We have to search that elements starting index to do that Modified Binary Search.

Step1--ELE=A[n/2]

Step2:--Search for starting index of ELE with in range of 1 to n/2-1 which is sorted array. O(logn) time cost of modified binary search.

Now after find such index say i Now see if A[i] ==A[ i+ n/2 ] then it is the majority Ele (Cz Sorted array) else no majority Ele present. Above done in O(1).

So overall time complexity O(logn)+O(1)=O(logn)

Hence Option B is Ans.
+2
indeed the best one.
+1
easyly understandable.
0
Why are we determining position of x.?Isn't x input to the algorithm?
0

Fool proof way to find is, to perform 2 binary searches, one for n-1 and other for n+1.

Even if n-1 and n+1 are not present, we can modify BST to return the index where min,max are equal.

Then check the difference between two resuls, if greater than n/2.

Hence 2logn comparisons required and answer is B.

1
2