# How find the highest number of frequency in a range of number?

Page 1 of 1

## 3 Replies - 1437 Views - Last Post: 04 August 2013 - 10:41 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=326380&amp;s=3b26da8a1d7af19d35d9ee5478740b2a&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

• New D.I.C Head

Reputation: 0
• Posts: 2
• Joined: 28-February 13

# How find the highest number of frequency in a range of number?

Posted 04 August 2013 - 12:47 AM

I am given a range of numbers in a non-descending order. Now in the query I have find the frequency number of the highest frequency. I tried to build a segment tree of the maximum frequencies. but I am having problem writing the query program. Here's my code

#include <iostream>
#include <map>
using namespace std;
int left(int p) { return p<<1; }
int right(int p) { return (p<<1)+1; }
int parent(int p) { return p>>1; }
void buildTree(int *A,int *st,int p,int L,int R,map<int,pair<int,int> > &strtEnd)
{
if(L==R)
st[p]=1;
else
{
buildTree(A,st,left(p),L,(L+R)/2,strtEnd);
buildTree(A,st,right(p),(L+R)/2+1,R,strtEnd);
if(A[(L+R)/2]==A[(L+R)/2+1])
{
int cnt = strtEnd[A[(L+R)/2]].second-strtEnd[A[(L+R)/2]].first+1;
st[p] = max(max(st[left(p)],st[right(p)]),cnt);

}
else
st[p] = max(st[left(p)],st[right(p)]);
}
}
int query(int *A,int *st,int p,int L,int R,int i,int j)
{
if(R<i||L>j) return -1;
if(L>=i&&j>=R) return st[p];
// now what??

}

int main()
{

int n;
int A[n];
map<int,pair<int,int> > first_last;
for(int i = 0;i<n;++i)
{
cin>>A[i];
if(i==0)
first_last[A[i]].first = i;
else if(i==n-1)
first_last[A[i]].second = i;
else if(A[i]!=A[i-1])
{
first_last[A[i-1]].second = i-1;
first_last[A[i]].first = i;

}

}
int st[4*n+2];
buildTree(A,st,1,0,n-1,first_last);
int queries;
cin>>queries;
while(queries--)
{
int i,j;
cin>>i>>j;
cout<<query(A,st,1,0,n-1,i,j);

}

}

I am really having trouble designing the query program.I am also having segmentation fault with my buiild function. />

Is This A Good Question/Topic? 0

## Replies To: How find the highest number of frequency in a range of number?

### #2 Michael26

• May the Schwartz be with you

Reputation: 395
• Posts: 1,601
• Joined: 08-April 09

## Re: How find the highest number of frequency in a range of number?

Posted 04 August 2013 - 05:29 AM

Can't you use Hashtable, for each element in the array, do like counts[element] = counts[element] + 1 .
When you are done, loop through the map and find the max.

• New D.I.C Head

Reputation: 0
• Posts: 2
• Joined: 28-February 13

## Re: How find the highest number of frequency in a range of number?

Posted 04 August 2013 - 07:05 AM

Michael26, on 04 August 2013 - 05:29 AM, said:

Can't you use Hashtable, for each element in the array, do like counts[element] = counts[element] + 1 .
When you are done, loop through the map and find the max.

There numbers range from -100000 to 100000.There is negative numbers. So, hashing doesn't seems possible..

### #4 Skydiver

• Code herder

Reputation: 4823
• Posts: 15,950
• Joined: 05-May 12

## Re: How find the highest number of frequency in a range of number?

Posted 04 August 2013 - 10:41 AM

Hashing will work as long as you use a suitable hash function that maps negative numbers to appropriate slots in the hash table.