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?
2 Answers 2
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;
}
}
-
\$\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\$lightning_missile– lightning_missile2014年11月30日 08:40:42 +00:00Commented Nov 30, 2014 at 8:40
-
\$\begingroup\$ @morbidCode: Not going to do all the work for you. Think about it a bit, \$\endgroup\$Loki Astari– Loki Astari2014年11月30日 11:24:57 +00:00Commented Nov 30, 2014 at 11:24
-
\$\begingroup\$ I thought about it, and I fixed it. I just thought you made a bug. \$\endgroup\$lightning_missile– lightning_missile2014年11月30日 12:53:04 +00:00Commented Nov 30, 2014 at 12:53
-
\$\begingroup\$ I did. But not worth worrying about (that is what compilers do). \$\endgroup\$Loki Astari– Loki Astari2014年11月30日 18:36:32 +00:00Commented Nov 30, 2014 at 18:36
Few remarks:
- The variable
i
of the testcase loop is not use and it is masked by the nexti
loop, you could simply use awhile 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';
}
}
-
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\$Loki Astari– Loki Astari2014年11月29日 18:17:06 +00:00Commented Nov 29, 2014 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\$Loki Astari– Loki Astari2014年11月29日 18:19:06 +00:00Commented Nov 29, 2014 at 18:19 -
\$\begingroup\$ I understand the argument, I will edit my answer. \$\endgroup\$Blabla404– Blabla4042014年11月29日 20:44:50 +00:00Commented Nov 29, 2014 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\$lightning_missile– lightning_missile2014年11月30日 08:52:53 +00:00Commented Nov 30, 2014 at 8:52
-
\$\begingroup\$ Nope you are right, I confused number and numberCount \$\endgroup\$Blabla404– Blabla4042014年11月30日 11:25:48 +00:00Commented Nov 30, 2014 at 11:25