Count of Maximum - CodeChef

Question

I'm doing an easy problem in codechef. Here's the problem statement for maxcount:

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.

OK, I cheated. I used std:map because I want to play with it. Please review my code:

#include<iostream>
#include<map>

int main() {
    int test_cases{};
    std::cin >> test_cases;
    for (auto i = 0; i < test_cases; ++i) {
        std::map<int,int> count;
        std::size_t size{};
        std::cin >> size;
        int x{};
        for (std::size_t i = 0; i < size; ++i) {
            std::cin >> x;
            count[x] = ++count[x];
        }
        int number{};
        int numberCount{};
        for (auto& i : count) {
            if (i.second > numberCount) {
                number = i.first;
                numberCount = i.second;
            } else if (i.second == numberCount) {
                if (i.first < number) {
                    number = i.first;
                }
            } else {
                continue;
            }
        }
        std::cout << number << " " << numberCount << '\n';
    }
}

How can I make this better and faster?

Answer 1

Simplify:

        count[x] = ++count[x];

        // Why not just;
        ++count[x];

Variable name length:

for (auto i = 0; i < test_cases; ++i) {

Have you ever tried searching for all occurrences of the variable i in the resulting loop. The number of false positives will be a pain in the arse. Name your loop variables so you can find them easily.

Hiding variables names:

    for (std::size_t i = 0; i < size; ++i) {

Though not technically illegal. This becomes a maintenance problem. It's OK for you today as you just wrote the code. But for anybody else (or you in years time) this is can be a pain. Try and give your variables unique meaningful names (self documenting code is a brilliant practice but it requires variable names to be meaningful).

The whole loop where you search for the largest repeat:

    for (std::size_t i = 0; i < size; ++i) {

This can be done inline while you were counting. I would not have a second loop to work it out after the fact.

I would simplify this condition:

} else if (i.second == numberCount) {
            if (i.first < number) {

// I find it easier to read as:

} else if (i.second == numberCount) && (i.first < number) {

This seems a bit redundant:

        } else {
            continue;
        }

Personally I think initializing integers with {} looks terrible (and is slightly confusing).

std::size_t size{};

std::size_t size = 0;  // Much easier to read.

Whats the point in initizliaing a variable just before you write over it?

    std::size_t size{};   // Why initialize it here
    std::cin >> size;     // Only to trash the initialization here.

Address Comments:

    int number{};
    int numberCount{};
    for (std::size_t i = 0; i < size; ++i) {

        std::cin >> x;
        std::size_t&  countV = count[x];

        ++countV;

        if (countV > numberCount || (countV == numberCount && x < number))
        {
            number      = x;
            numberCount = countV;
        }
    }

Answer 2

Few remarks:

• The variable i of the testcase loop is not use and it is masked by the next i loop, you could simply use a while loop to not use any extra variable
• It would be better to declare x inside the for loop, since it is only use here.
• the line count[x] = ++count[x] is extremely confusing and a minor modification (count[x] = count[x]++) is an undefined behaviour. You should simply use ++count[x].
• Since map is an ordered container your else if is useless.
• Also doing just a else{continue} at the end of the loop is useless.
• You do not need to use {} to default initialise your variables.
• number should be initialised with meaningful value
• your code does not handle the case where the number of element is 0

Here is the code with my suggested improvements

#include <iostream>
#include <map>

int main() {
    int test_cases;
    std::cin >> test_cases;
    while(test_cases--) {
        std::map<int,int> count;
        std::size_t size;
        std::cin >> size;
        for (std::size_t i = 0; i < size; ++i) {
            int x;
            std::cin >> x;
            ++count[x];
        }
        int number;
        int numberCount = 0;
        for (auto& i : count) {
            if (i.second > numberCount) {
                number = i.first;
                numberCount = i.second;
            }
        }

        //if(numberCount == 0)
        //does something to handle the empty collection

        std::cout << number << ' ' << numberCount << '\n';
    }
}