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;
 }
 }

• lightning_missile: 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}'"
• Loki Astari: @morbidCode: Not going to do all the work for you. Think about it a bit,
• lightning_missile: I thought about it, and I fixed it. I just thought you made a bug.
• Loki Astari: I did. But not worth worrying about (that is what compilers do).

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';
 }
}

• Loki Astari: 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.
• Loki Astari: 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
• Blabla404: I understand the argument, I will edit my answer.
• lightning_missile: 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?
• Blabla404: Nope you are right, I confused number and numberCount