Question

Describe an algorithm that, given a list of n numbers, decides in linear time whether the list contains at least ⌈n/2⌉ numbers, all with equal value.

What if we want to know if there are at least ⌈ n/100 ⌉ numbers with equal value?

Hint: suppose some number, x, occurs ⌈n/2⌉ times. Where could all of these copies end up if we sorted? (This is not a suggestion we should actually sort). Wherever they end up, find one invariant.

Answer 1

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

• Function checkSame(A,k)
  • A=sort(A)//Merge sort the list A
  • Define and initalize ct=1
  • Define and INITIALIZE total=ceil(n/k)
  • For i=0 to A.length-2 do
    • IF A[i]==A[i+1]
      • ct=ct+1
    • Else
      • IF ct==total
        • RETURN TRUE
      • EndIf
      • ct=1
    • EndIf
  • EndLoop
  • IF ct==total
    • RETURN TRUE
  • EndIf
  • RETURN FALSE
• EndFunction

To run the algo for n/2 use it as checkSame(A,2)

To run it as n/100 use it as checkSame(A,100)

The Time complexity of above algo is O(n*log(n))

Kindly revert for any queries

Thanks.