Algorithm
Problem link- https://www.spoj.com/problems/DCEPCA09/
DCEPCA09 - MMM
Everyone knows how to find mean, median and mode of an array of numbers. For people who don’t know this, here is the description:
- Mean is the arithmetic average of a set of values.
- Median of a finite list of numbers can be found by arranging all the observations from lowest value to highest value and picking the middle one. If there is an even number of observations, then there is no single middle value; the median is then usually defined to be the mean of the two middle values.
- The mode is the value that appears most often in a set of data. If more than one number is applicable to be the mode, select the highest value number amongst them as the mode.
The problem is just to find these 3 values. Given an array of numbers and two indices i and j, find the mean, median and mode of elements in the interval i to j including numbers at indices i and j. Note that i and j are 0 index based.
Constraints
2 <= N <= 10000
1 <= Q <= 10000
0 <= A[i] <= 10^8
0 <= i < N
i <= j < N
Input
First line contains N which is the total number of numbers in the array. The next line contains N numbers A[i] which are the elements of the array. Next line contains a number Q which defines the total number of queries we are making for the interval i to j. It is followed by Q lines each containing 2 numbers i and j which denotes the indices to be queried for.
Output
Print Q lines each containing 3 numbers Mean, Median and Mode respectively. If the answer for any case comes to be a floating point, then take the integer part of the number as the answer. For example: if mean, median and mode comes up to be 6.44 7.8 9 then the final answer is 6 7 9.
Example
Input: 5
6 5 3 7 7
2
1 2
0 4
Output: 4 4 5
5 6 7
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
#define MOD 1000000007LL
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
template <typename T>
using ordered_set = tree<T, null_type, less < T>, rb_tree_tag,tree_order_statistics_node_update>;
const int N = 1e4+5;
const int M = 1e4+5;
const int SQN = sqrt(N) + 1;
struct query{
int l, r;
int idx;
int block;
query(){}
query(int _l, int _r, int _id){
l = _l;
r = _r;
block = _l/SQN;
idx = _id;
}
bool operator < (const query &b) const{
if(block != b.block)
return block < b.block;
return r < b.r;
}
};
query Q[M];
ll arr[N];
ll mean[M], median[M], mode[M], n, q;
set<pair<int, int>, greater<pair<int, int> > > occ;
unordered_map<int, int> mapped;
ordered_set<pair<int, int> > T;
int get_med(int size){
if(size&1) return T.find_by_order(size/2)->first;
else return (T.find_by_order(size/2)->first+T.find_by_order(size/2-1)->first)/2;
}
int main(){
scanf("%lld", &n);
for(int i = 0; i < n; i++)
scanf("%lld", arr+i);
scanf("%lld", &q);
for(int i = 0; i < q; i++){
int l, r;
scanf("%d%d", &l, &r);
Q[i] = query(l, r, i);
}
sort(Q, Q+q);
int curl = 0, curr = -1;
ll sum = 0;
int iter = 0;
for(int i = 0; i < q; i++){
int l = Q[i].l;
int r = Q[i].r;
int id = Q[i].idx;
while(curr < r){
++curr;
T.insert({arr[curr], iter++});
sum += arr[curr];
occ.erase({mapped[arr[curr]], arr[curr]});
mapped[arr[curr]]++;
occ.insert({mapped[arr[curr]], arr[curr]});
}
while(curl > l){
--curl;
T.insert({arr[curl], iter++});
sum += arr[curl];
occ.erase({mapped[arr[curl]], arr[curl]});
mapped[arr[curl]]++;
occ.insert({mapped[arr[curl]], arr[curl]});
}
while(curr > r){
T.erase(T.find_by_order(T.order_of_key({arr[curr], -1})));
sum -= arr[curr];
occ.erase({mapped[arr[curr]], arr[curr]});
mapped[arr[curr]]--;
occ.insert({mapped[arr[curr]], arr[curr]});
--curr;
}
while(curl < l){
T.erase(T.find_by_order(T.order_of_key({arr[curl], -1})));
sum -= arr[curl];
occ.erase({mapped[arr[curl]], arr[curl]});
mapped[arr[curl]]--;
occ.insert({mapped[arr[curl]], arr[curl]});
++curl;
}
mean[id] = sum/(r-l+1);
median[id] = get_med(r-l+1);
mode[id] = occ.begin()->second;
}
for(int i = 0;i < q; i++)
printf("%lld %lld %lld\n", mean[i], median[i], mode[i]);
return 0;
}Input
6 5 3 7 7
2
1 2
0 4
Output
5 6 7
Demonstration
SPOJ Solution-DCEPCA09 - MMM-Solution in C, C++, Java, Python