The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+32 votes
3.5k 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)$

asked in Algorithms by Veteran (68.8k points) | 3.5k views
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.
this ques is purely based on how efficiently you read the question.

@ mcjoshi

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

@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

5 Answers

+34 votes
Best answer

answer = option B

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.

answered by Veteran (30.5k points)
edited by
Then it should be (B)
Why do we need to  count the numbe rof occurrences of the element?..we just need to find whether i occurs more than n/2 times or not..and that can be done in O(1) time..isnt it? ,by checking the middle and next element..please clarify.
It may be the case that an integer does not appear more than n/2 times but appears at all those locations where you are suggesting the checks.
suppose

1 3 4 4 4 4  4 6 7 9

4 occurs in middle but not  majority by n/2

it is present both in middle as well as the neighbourhood.

The algo checks to find the position of frst occurance of 4.

here for 4 it is,3

>n/2 times means

there should be span of n/2 4 s,since element are in sorted order,nothing between span of 4 s.

Hence,i+n/2 th index must also be 4 .here it is not ,so here 4 is not occurring > n/2

core of the algo is a BS which is logn
@amar
I think your last statement is wrong. O(log n) would be needed to find "an integer" and O(1) would be needed to check if its present more than n/2 times. Recheck.
Read example given by GateMm, it should make you understand.
"It may be the case that an integer does not appear more than n/2 times but appears at all those locations where you are suggesting the checks." Can you give sone examples for such situations and which also agrees with the guven question?

example : 1 3 4 4 4 4 4 6 7 9

See $4$ appears 5 times only. But according to the question to be a majority element it should appear more than $\frac{10}{2}=5$ times i.e. atleast 6 times it should appear in the array. Here $\mathcal{O}(1)$ time solution FAILS.

Thank You
Actually in the sorted array if an element is present more than than n/2 times then it must be present in the middle element so in a sorted array we can find in O(1) time and to locate the element where it ends and where it starts we have to take a binary search which is O(log n) time so total O(log n) time.
Beautiful Answer :)

Does Divide and Conquer work here ?
I know I have to count occurrences of middle element.
I will divide array into two halves, then i will count occurrance of that element indivisually, then i will combine and check if total occurance if greater than n/2 or not.
Like this
 

mid=n/2
Count_occurrance(i,j)
{
if(i==j && A[i] == A[mid])
return 1;
if(i==j && A[i] != A[mid])
return 0;
else if (A[(i+j)/2] = A[mid])
      return(1+Count_occurrance(i, k)+Count_occurrance(k+1,j))    //here k is (i+j)/2
     else
      return(Count_occurrance(i, k)+Count_occurrance(k+1,j))
}



this is
T(n) = 2T($\frac{n}{2}$)+c
which gives $logn$.

Is this ok ?

Only binary search, will it work good?
Say if 1233346
will this not violate assumtion?
u have 7  elements means (n=7) here 1233346...and "3" is present only 3 times but in question it says that  it should be present more (n/2) times which is must be greater than 3.5..means at least 4 times it should present..according to me..
@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
Read this :http://www.geeksforgeeks.org/check-for-majority-element-in-a-sorted-array/
Thanks for valuable reference and help. I was not thinking properly.
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)

@rajatmyname,

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. 

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

+23 votes

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

 

 

 

answered by Veteran (13.8k points)
its An integer not The integer, so we should determine first what is the Integer $x$
+15 votes
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.
answered by Veteran (22.7k points)
indeed the best one.
easyly understandable.
Why are we determining position of x.?Isn't x input to the algorithm?
+2 votes

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.

answered by Loyal (3.3k points)
+1 vote
answered by Junior (679 points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

32,330 questions
39,146 answers
108,247 comments
36,501 users