3
\$\begingroup\$

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?

\$\endgroup\$
3
\$\begingroup\$

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;
        }
    }
\$\endgroup\$
4
  • \$\begingroup\$ std::size_t& countV = count[x]; didn't work for me because it looks like we can't initialise an int into an unsigned reference? Compiler says "invalid initialization of reference of type 'std::size_t& {aka unsigned int&}' from expression of type 'std::map<int, int>::mapped_type {aka int}'" \$\endgroup\$ Nov 30 '14 at 8:40
  • \$\begingroup\$ @morbidCode: Not going to do all the work for you. Think about it a bit, \$\endgroup\$ Nov 30 '14 at 11:24
  • \$\begingroup\$ I thought about it, and I fixed it. I just thought you made a bug. \$\endgroup\$ Nov 30 '14 at 12:53
  • \$\begingroup\$ I did. But not worth worrying about (that is what compilers do). \$\endgroup\$ Nov 30 '14 at 18:36
2
\$\begingroup\$

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';
    }
}
\$\endgroup\$
5
  • 2
    \$\begingroup\$ it could be a good idea to use using namespace std Nope bad idea: -1 As this contradicts every other code review done on this site. Its not the fact that the code is simple but it ingrains a bad habit that will cause accidents when writing real code. Remove it and I will remove the -1. \$\endgroup\$ Nov 29 '14 at 18:17
  • 1
    \$\begingroup\$ In fact I will give you a +1 for a case that I missed your code does not handle the case where the number of element is 0 \$\endgroup\$ Nov 29 '14 at 18:19
  • \$\begingroup\$ I understand the argument, I will edit my answer. \$\endgroup\$
    – Blabla404
    Nov 29 '14 at 20:44
  • \$\begingroup\$ int number = 0; - but if there is no elements, the user might think 0 is a real element because 0 can also be an element in the map right? Isn't setting numberCount to 0 then handle the case if numberCount remains 0 (no elements) after the loop better? Or I'm missing something? \$\endgroup\$ Nov 30 '14 at 8:52
  • \$\begingroup\$ Nope you are right, I confused number and numberCount \$\endgroup\$
    – Blabla404
    Nov 30 '14 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.