You are not logged in. Please login at www.codechef.com to post your questions!

×

[closed] COUNT OF MAXIMUM REPEATING ELEMENT IN THE ARRAY

how to find the count of an element which repeats maximum number of times in an array if the array contains both positive and negative elements in most efficient way ?
in O(n)?

asked 27 Jun '14, 14:53

suryanit's gravatar image

4★suryanit
11234
accept rate: 0%

closed 29 Jun '14, 00:56

garakchy's gravatar image

1★garakchy
1.1k163048

@suryanit: If you have understood the answer can you please accept the answer so that we can close this question . :)

(28 Jun '14, 22:41) bipin23★

The question has been closed for the following reason "The question is answered, right answer was accepted" by garakchy 29 Jun '14, 00:56


I am not sure can you try this with map? Take a look at this codehere

By using MAP we have get the count with lesser time complexity i mean by O(n)=log n. I guess that will be better than O(n) :)

If you can tell the question then we can give a try.

This is the code i submitted to find out the maximum count element in an array. I mean for the MAX_COUNT problem.

link

answered 27 Jun '14, 15:19

bipin2's gravatar image

3★bipin2
3.1k254671
accept rate: 8%

edited 28 Jun '14, 13:48

Can you please tell whether it is working or not? Or tell the question?

(27 Jun '14, 18:39) bipin23★
2

this is the best method

(28 Jun '14, 14:16) kuruma3★
1

@kuruma: thanks dude. It is a bit disappointing that even after debugging the whole wrong code submitted here and theses ppl they dont even turn back after getting the benifit :( Not even just a thanks or an up-vote. I dont know whether he is satisfied with this method :\ Anyway thanks @kuruma :D glad to find you here again :)

(28 Jun '14, 17:00) bipin23★

how is this the best method? the element access time of a map is O(log(n)). the element access time(element look up) of an array is always O(1). So, when you update the frequency at some index in a map, it takes O(log(n)) but it takes only O(1) in an array.

So, if both methods can be used and the time limit is strict, shouldn't we try to use an array
For example: std::map< int,int > m;
m[i]++; updation will have O(log(n)) complexity
but in case of an array int m[1000];
m[i]++; will have O(1) complexity

This is something to consider when we solve the problem.

(28 Jun '14, 17:20) pratku1234★

Read the question properly @pratku123. the range is between -10^9 to 10^9. How can you store the frequency of negative numbers in array index?

(28 Jun '14, 19:51) bipin23★

@bipin2 Thanks for the clarification. In that case, this method is the best. Good Answer!

(28 Jun '14, 22:24) pratku1234★

@pratku123: thanks bro!! Suggestions are always welcome :)

(28 Jun '14, 22:38) bipin23★
showing 5 of 7 show all

If the range of elements are small that is in the range of <=10^6 we can create a frequency array say FREQ. For each element the count in the frequency array we have to increment. Initially all values in FREQ are zeros. When you start reading input and say you read a number x, you should add 1 to FREQ[x]. It takes O(N) time to build this array after initialization. When all input values have been scanned, one could make iteration at the FREQ array to find the smallest element with the largest count.

By using O(N) you can find the largest element in the frequency array and save the index of the largest number in the FREQ array and that will be the answer :)

But this will work only for +ve numbers :( i did not see the last portion. Sorry HAPPY CODING

link

answered 27 Jun '14, 15:03

bipin2's gravatar image

3★bipin2
3.1k254671
accept rate: 8%

edited 27 Jun '14, 15:14

range of elements -10^9 to 10^9

(27 Jun '14, 15:14) suryanit4★

how to build frequency array for negative elements?

(27 Jun '14, 15:14) suryanit4★

I have posted another method.

(27 Jun '14, 15:44) bipin23★

Both the methods mentioned in answers before my answer,
1. Using a map.
2. Using an array.
Can be used, depending on the question.
The interesting thing here is that,
the element access time of a map is O(log(n)). Detailed discussion: link1 and link2
the element access time(element look up) of an array is always O(1).
So, when you update the frequency at some index in a map, it takes O(log(n)) but it takes only O(1) in an array.

So, if both methods can be used and the time limit is strict, try to use an array
For example: std::map< int,int > m;
m[i]++; updation will have O(log(n)) complexity
but in case of an array int m[1000];
m[i]++; will have O(1) complexity

link

answered 27 Jun '14, 19:49

pratku123's gravatar image

4★pratku123
1.8k4933
accept rate: 14%

Well I have an idea. If the numbers can be negative or large (eg: 10^9), then arrays cannot be used. Then we are using map and time complexity will be nlogn. But this will also have lot of dynamic memory allocation factors, etc that slow down the code.

So, a simpler way is to sort the array in O(nlogn) and then traverse it to find the most repeating element.

link

answered 28 Jun '14, 17:40

yash_15's gravatar image

5★yash_15
5181716
accept rate: 2%

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,738
×862
×26
×4

question asked: 27 Jun '14, 14:53

question was seen: 5,882 times

last updated: 29 Jun '14, 00:56