2
\$\begingroup\$

I have been learning C++ for the past 2 weeks.

Following is a problem I solved from Hackerrank. I am somewhat unsure if it's the correct way to solve this, even though I got the desired output. How can I improve this?

Given an array of bird sightings where every element represents a bird type id, determine the id of the most frequently sighted type. If more than 1 type has been spotted that maximum amount, return the smallest of their ids.

Input Format

The first line contains an integer representing the number of observations. The second line consists of space-separated integers, each a type number of the bird sighted.

My code:

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
int main()
{
    int n, input;
    vector<int> arr;
    cin >> n;
    while (n--)
    {
        cin >> input;
        arr.push_back(input);
    }
    int max_count = 0, count=0, max_id;//here max_id is our answer
    //sorting the array
    sort(arr.begin(), arr.end());
    for (int i = 1; i < (int)arr.size(); i++)
    {
        if (arr[i] == arr[i - 1])
        {
            count++;
            if (count > max_count)
            {
                max_count = count;//setting the new max count
                max_id = arr[i];//setting the new max-count id
            }
            else if (count == max_count)
            {
                max_id = (arr[i] < max_id ? arr[i] : max_id);//checking the lowest 
            }
        }
        else {
            count = 0;
        }
    }
    

    cout << max_id << endl;
    return 0;
}
\$\endgroup\$

1 Answer 1

6
\$\begingroup\$

I don't know where you've been learning C++, but please avoid anything that presents using namespace std as good practice. It serves to remove one of the benefits of C++ and can actually cause your program to behave in unexpected ways. Stop using that, and instead get used to writing the (intentionally very short) std:: prefix where it's needed.

When we read from std::cin using >>, we should always check the state of the stream before using the streamed-to value. If std::cin is in an error state, then we can't trust what was read, and should abort, rather than continuing with invalid data.

When writing to an output stream, we rarely need to force it to be flushed. We normally want a plain newline (which doesn't flush) and almost never need std::endl. Remember that streams will be flushed when the program exits.

When we know how many observations we'll be reading, it's a good practice to reserve capacity in the vector. This makes it more efficient, as we then know it won't need to resize itself as more input arrives:

arr.reserve(n)

Instead of casting the array size to int, it's probably better to make the type of i match the size - that would be std::size_t i.

There's a bug: the program doesn't produce the correct results if all the sightings are unique (i.e. if all the counts are 1). To fix that, we need to initialise max_id to arr[0] (after the sort(), of course), rather than to 0.

Since we sorted the array, the test within if (count == max_count) isn't necessary. The sorting means that max_id < arr[i], so we don't need to do anything there.

There are algorithms in the standard library that would help simplify the code - look at std::upper_bound() for finding the next element in the vector that's greater than a particular value, and consider how you could use that to count.

We could make the code much simpler by choosing a container type that's much better for counting, though. We could consider a std::multiset, but I think the best choice would be a std::map<int, std::size_t>. Our input loop would then be

while (n--) {
    int input;
    if (!(std::cin >> input)) {
        return EXIT_FAILURE;
    }
    ++counts[input];
}

We can then use the std::max_element() algorithm to find the element with most sightings - we'll need to pass a comparator function that compares values, but it won't need to compare the ids, because std::max_element() returns the earliest element when there are two or more equal maxima, and a std::map is sorted smallest-first.

Assuming we're using C++20, we can use the Ranges version of max_element(), in which we simply need to pass a projection rather than writing our own comparator.


Modified code

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <map>

int main()
{
    using id_map = std::map<int, std::size_t>;

    std::size_t n;              // First input - number of sightings
    if (std::cin >> n; !std::cin) {
        std::cerr << "Failed to read count\n";
        return EXIT_FAILURE;
    }

    if (n == 0) {
        return EXIT_FAILURE;    // no sightings, so no output
    }

    id_map counts;              // Read and count the sightings
    while (n--) {
        if (int input; std::cin >> input) {
            ++counts[input];
        } else {
            std::cerr << "Failed to read id\n";
            return EXIT_FAILURE;
        }
    }

    // Find the modal element (lowest id if there's a tie)
    auto max_it = std::ranges::max_element(counts, std::less<>{},
                                           &id_map::value_type::second);
    std::cout << max_it->first << '\n';
}
\$\endgroup\$
3
  • 1
    \$\begingroup\$ A structured binding would be nice to avoid the->first: auto [max_value, max_count] = ...; std::cout << max_value << '\n'; \$\endgroup\$
    – G. Sliepen
    Mar 13, 2022 at 13:05
  • \$\begingroup\$ Yes, that helps give names to the first and second. OTOH, for some reason I always feel reluctant to write = *function(…). The dereference is easily overlooked. \$\endgroup\$ Mar 13, 2022 at 17:23
  • 1
    \$\begingroup\$ Counting elements is called a "histogram", in case that's useful to future readers looking for how to optimize it or for more info about it. It's would be the first step of a counting-sort, but as you say, for this it's much better to use the counts directly instead of expanding back into an array with duplicates. \$\endgroup\$ Mar 13, 2022 at 20:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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