Frequency Counting and Counting Arrays

Frequency counting replaces repeated searches for identical values with a record of how many times each value occurs. It supports duplicate detection, distinct counts, mode selection and multiset comparisons. A small dense universe fits an indexed count array; large or negative keys need a map, hashing or compression. Our program offers an array mode for digits and an ordered-map mode for arbitrary bounded signed integers.

Prerequisites: Arrays; loops; basic STL container interfaces.

Build the idea

1. 1. Define the frequency invariant

   After reading a prefix, frequency[value] equals the number of times that value has appeared. Initialize every counter to zero, then increment exactly one entry for each input occurrence. Counting distinct values means counting positive entries, not summing their frequencies. The sum of all frequencies should equal n, which is a useful debugging invariant.

2. 2. Choose an array only for a valid range

   Mode A accepts values 0..9 and uses ten counters. Direct access is constant-time, the storage is tiny, and scanning possible keys is cheap. For keys −10^12..10^12, allocating an array covering every possible value is absurd. Subtracting an offset works only when the full range width is safely small, not merely because n is small.

3. 3. Use a map for sparse signed keys

   Mode M stores map<long long,int>. Incrementing frequency[x] creates a missing key with zero count, then adds one. Ordered map operations take O(log d) with d stored distinct keys and iteration is by increasing key. An unordered_map has expected average constant operations but no sorted order and a linear worst case per operation; do not promise its speed unconditionally.

4. 4. Select a mode with an explicit tie rule

   Track bestCount and bestValue while scanning keys in increasing order. Replace only when a strictly larger frequency is found. This retains the smallest value on a tie. For [−2,7,−2,7,100], distinct is 3 and both −2 and 7 occur twice; −2 wins by the tie rule. Empty input has no most-frequent value, so print EMPTY rather than treating zero as an observed key.

5. 5. Connect counts to other problems

   A duplicate exists if some count exceeds one. Two sequences are equal as multisets when every key has the same frequency in both, regardless of order. For window queries, add and remove counts as endpoints change. Character counts are the same pattern on a fixed alphabet. Always separate the key representation from the statistic computed from its counts.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: 1. Define the frequency invariant After reading a prefix, frequency[value] equals the
// number of times that value has appeared.
#include<iostream>
#include<map>
int main(){
    char mode;
    int n;
    std::cin>>mode>>n;
    int distinct=0,bestCount=0;
    long long bestValue=0;
    if(mode=='A'){
        int frequency[10]={};
        for(int i=0;i<n;++i){
            int x;
            std::cin>>x;
            ++frequency[x];
        }
        for(int value=0;value<10;++value){
            if(frequency[value]>0){
                ++distinct;
                if(frequency[value]>bestCount){
                    bestCount=frequency[value];
                    bestValue=value;
                }
            }
        }
    }
    else{
        std::map<long long,int>frequency;
        for(int i=0;i<n;++i){
            long long x;
            std::cin>>x;
            ++frequency[x];
        }
        for(const auto&entry:frequency){
            ++distinct;
            if(entry.second>bestCount){
                bestCount=entry.second;
                bestValue=entry.first;
            }
        }
    }
    std::cout<<distinct<<'\n';
    if(n==0){
        std::cout<<"EMPTY\n";
    }
    else{
        std::cout<<bestValue<<' '<<bestCount<<'\n';
    }
}

Complexity analysis

Mode A: O(n+10) time and O(10) auxiliary storage. Mode M: O(n log(d+1)+d) time and O(d) storage, d≤n, using an ordered map. The program streams input rather than storing all values. Counts fit int for n≤200000; keys use long long for |value|≤10^12.

Example input and output

Read mode n, mode A (all values 0..9) or M (signed values |value|≤10^12), 0≤n≤200000, then n values. Print distinct count, then the smallest most-frequent value and its count, or EMPTY.

Input

M 5
-2 7 -2 7 100

Output

3
-2 2

Distinct values are −2,7,100. The first two tie at frequency 2, so −2 is selected.

Practical applications

Use arrays for small bounded alphabets, maps for sparse ordered keys and compression for large known-offline keys used with indexed data structures. Frequency counting is often a simpler first step than sorting every time, but the best representation depends on range size, online requirements and desired output order.

Check your understanding

When is a frequency array appropriate?

Put it into practice

Print how many equal unordered pairs of indices the input contains.