Count of Maximum Solution

Problem

Given an array A of length N, your task is to find the element which repeats in A maximum number of times as well as the corresponding count. In case of ties, choose the smaller element first.

Codechef Problem Link

Input

First line of input contains an integer T, denoting the number of test cases. Then follows description of T cases. Each case begins with a single integer N, the length of A. Then follow N space separated integers in next line.

Output

For each test case, output two space separated integers V & C. V is the value which occurs maximum number of times and C is its count.

Constraints

  • 1 <= T ≤100
  • 1 <= N ≤100
  • 1 <= A[i] <= 10000

Sample Input

2
5
1 2 3 2 5
6
1 2 2 1 1 2

Sample Output

2 2
1 3

Solution

//
//  main.cpp
//  Count of Maximum
//
//  Created by Himanshu on 18/02/22.
//

#include <iostream>
#include <map>
#include <climits>
using namespace std;

int main() {
    int T, n;
    cin>>T;
    
    while (T--) {
        cin>>n;
        
        int *a = new int[n]();
        map<int, int> hashMap;
        int maxCount = 0;
        int smallInt = INT_MAX;
        
        
        for(int i=0; i<n; i++) {
            cin>>a[i];
            hashMap[a[i]]++;
        }
        
        for (const auto& kv: hashMap) {
            if (kv.second > maxCount) {
                maxCount = kv.second;
                smallInt = kv.first;
            } else if (kv.second == maxCount) {
                if (smallInt > kv.first) {
                    smallInt = kv.first;
                }
            }
        }
        
        cout<<smallInt<<" "<<maxCount<<endl;
    }

    return 0;
}

Time Complexity: O(min(N, A[i]))

Leave a Reply

Your email address will not be published.