GATE CSE 2008 | Question: 40

Question

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

• A. $\Theta(n)$
• B. $\Theta(\log n)$
• C. $\Theta(\log^*n)$
• D. $\Theta(1)$

Comments

😎

---

what is log*n means ?

---

kira204 generally $log^{*}$ is prefered to power of $log$ for ex-$log^{2}n= (logn)^{2}$

Answer 1

Answer is 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.

Comments

@Sachin Mittal 1 sir,

in your code

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))

here in else we can simply return 0 because if that element is not present in the mid position then it is obviously not having more than n/2 occurrance’s .

please check once!

---

I think this can be done in O(1). As we must first check middle element and then compare it with 1^st and last element of array. If it matches with any one of these, we can say that an integer appeared more than n/2 times else not.

---

@nishantsharma fails for 01112

Answer 2

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.

Comments

Why are we determining position of x.?Isn't x input to the algorithm?

---

Best Answer. ++ Vote

---

very thorough and easily interpreted....nice one

Answer 3

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

Comments

its An integer not The integer, so we should determine first what is the Integer $x$

---

thanks

Answer 4

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.

Comments

But what if the element (x-1) and (x+1) are also present multiple times/ O(n) times?