Register

Algorithm-Find most frequently occurring element in array

• edited by
836 views
0 0 votes

What is the running time for an algorithm which computes the most frequently occurring element of an array $A[1 \ldots n]$ ?

  1. $\mathrm{O}(\log \mathrm{n})$
  2. $\mathrm{O}(\mathrm{n})$
  3. $O(n \log n)$
  4. $\mathrm{O}\left(\mathrm{n}^{2}\right)$

1 Answer

1 1 vote

Assuming an array to be unsorted ,

we can maintain a count of occurence of each element in an other array , say count[] .We read an element from input array and increment that index of count[] which is the value in the input array.

So we get count of each element in 1 iteration over the input array.

Next by getting the maximum count from count array ,we can report the corresponding index of count array which is actually the element which is occuring most frequently.

Hence the correct answer should be B)

Voting & Accepting an answer helps improve the community
← Previous · Space Complexity of ...Next → · Ace Page# 128, Q#48
← Previous in category · Space Complexity of ...Next in category → · Ace Page# 128, Q#48
Position:
Show:

Related questions

9 9 votes
2 answers 2 answers
23.4k
23.4k views
radha gogia asked Jul 19, 2015
23,447 views
Given an unsorted array. The array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity?
(A) Insertion Sort with time complexity O(kn)(B) Heap Sort with time complexity O(nLogk)(C) Quick Sort with time complexity O(kLogk)(D) Merge Sort with time complexity O(...
0 0 votes
2 answers 2 answers
2.2k
2.2k views
venky.victory35 asked Dec 19, 2015
2,217 views
finding pair of an element in the array such that diff will be given no.
We are given a sequence of $n$ positive numbers $a_{1}, a_{2}, \ldots, a_{n}$ and a fixed number $k>0$. We want to find a pair of numbers $a_{i}$ and $a_{j}$ such that $j...
0 0 votes
2 2 answers
5.0k
5.0k views
nehab.sairam asked Jul 18, 2015
4,977 views
Let s be a sorted array of n integers. Let t(n) denote the time taken for the most efficient algorithm to determined if there are two elements with sum less than 1000 in s.What will be the time complexity???????
2 2 votes
1 1 answer
2.2k
2.2k views
yes asked Oct 6, 2015
2,215 views
the minimum no of comparisons required to find Majority Element in a sorted array (note that key is not given).
for example array contain a[1 2 3 3 3 3 3 4 5] then retun(1)