9
\$\begingroup\$

This is a problem from GeeksForGeeks and I have tried to solve it on my own and I have written this code.

Given an array of size n, the goal is to find out the smallest number that is repeated exactly ‘k’ times where k > 0? Assume that array has only positive integers and 1 <= arr[i] < 1000 for each i = 0 to n -1.

Examples:

Input:

arr[] = {2 2 1 3 1}
k = 2

Output: 1

Explanation:

Here in array:

  • 2 is repeated 2 times
  • 1 is repeated 2 times
  • 3 is repeated 1 time

Hence 2 and 1 both are repeated 'k' times

i.e 2 and min(2, 1) is 1

Input:

arr[] = {3 5 3 2}
k = 1

Output: 2

Explanation:

Both 2 and 5 are repeating 1 time but min(5, 2) is 2

How can I improve this code?

#include <iostream>
#include <vector>
#include <map>

template<class T>
void findElement(std::vector<T>& vec, int k)
{
  std::map<T, int> count;
  for(T x : vec)
  {
    count[x]++;
  }

  typename std::map<T, int>::iterator itr;
  for(itr = count.begin(); itr != count.end(); itr++)
  {
    if(itr->second == k)
    {
      std::cout << itr->first <<'\n';
      return;
    }
  }
  std::cerr << "No such element \n ";
}

int main()
{
  std::vector<char> v;
  v.push_back('r');
  v.push_back('t');
  v.push_back('q');
  v.push_back('r');
  v.push_back('u');
  v.push_back('q');
  v.push_back('s');
  int k;
  std::cout << " Enter the number of repetitions you want : ";
  std::cin >> k;
  std::cout << "The smallest element that has " << k <<" reptition is : ";
  findElement(v, k);
}
\$\endgroup\$
  • \$\begingroup\$ There is not much to talk about, except algorithm design. And may be other possible solution and situations in which they would be better. Though the current one is good for casual use already. \$\endgroup\$ – Incomputable Aug 27 '17 at 8:26
  • \$\begingroup\$ @Incomputable what I have to improve? I have used std::map instead of std::unordered_map because it sorts the element. \$\endgroup\$ – coder Aug 27 '17 at 8:29
11
\$\begingroup\$

Interface

  • There's no point in limiting your function inputs to a vector. You can take two input iterators instead. It'll make your function more flexible and more "standard library-like".

  • One function should do one focused thing. Your function finds such an element and prints it as the same time. These concerns are unrelated. You can return std::optional<T> instead to represent either such an element or its absence. Note: it works for C++17 only. You can use boost::optional or return a smart pointer if it's not available.

Modern C++

  • There's no need for things like this anymore:

    typename std::map<T, int>::iterator itr;
    for(itr = count.begin(); itr != count.end(); itr++)
    

    for (const auto& kv : count) is much better, isn't it?

  • You can also use initialization list to create a vector with the elements you need: std::vector<char> v({'r', 't',..., 's'})

Performance

  • for (T x : vec) creates an unnecessary copy. Use for (const T& x : vec) or for (const auto& T : vec) instead.

  • You can also use std::unordered_map to do the counting and then choose the smallest element (it's more efficient because one can find the minimum in O(n). It's "easier" than sorting the input). One caveat: you need a hash function for T in this case. You can pass it as another template parameter, defaulted to std::hash.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ One could also sort the vector/range and try to find the value with the appearance count. Though that would be sort plus linear pass, which is probably not good. The map would traverse only amount of distinct elements in a range. I guess it all depends on circumstances. \$\endgroup\$ – Incomputable Aug 27 '17 at 8:38
  • \$\begingroup\$ @Incomputable Yes, I believe that either option (map, unorded_map, sorting the vector) is reasonable. \$\endgroup\$ – kraskevich Aug 27 '17 at 8:39
  • \$\begingroup\$ How to take to input iterators instead of vector? \$\endgroup\$ – coder Aug 27 '17 at 8:56
  • \$\begingroup\$ @janos, the main issue here in my opinion is returning the iterator to the element inside of the container. Returning value rarely has any use in my experience. And it is weird for search to return found element by value anyway. Though your algorithm would be good for the specific use case. \$\endgroup\$ – Incomputable Aug 27 '17 at 8:56
  • \$\begingroup\$ @coder, the same way you take any other template argument. \$\endgroup\$ – Incomputable Aug 27 '17 at 8:56
6
\$\begingroup\$

Looking at the problem statement, a few obvious solutions come to mind:

  1. Count of many of each number there is and take the smallest with 'k' entries. This is what you do and as you are using a std::map with log(m) insertion where 'm' is the number of distinct elements (bounded by 1000) so you have \$O(n\log(m))\$ run time and \$O(m)\$ memory.
  2. Sort the input vector and scan linearly from the start until you find something that repeats 6 times. As you have to sort the whole thing you get \$O(nlogn)\$ time and \$O(n)\$ memory unless you can modify the input array.

But there is a better way:

/**
 * Will find the smallest value in 'vec' that is repeated 'k' times.
 *
 * It is assumed that values of 'vec' are [1, 1000[ as per 
 * problem description. 
 */
void findElement(const std::vector<unsigned int>& vec, int k){
  constexpr auto max_value = 1000U;
  std::array<unsigned int, max_value> freq;
  freq.fill(k);
  for(auto& value : vec){
      freq.at(value)--;
  }
  for(std::size_t f = 0; f < freq.size(); ++f){
      if(0 == freq[f]){
          std::cout << f <<'\n';
          return;
      }
  }
  std::cerr << "No such element\n";
}

The raw array is actually faster as this code only performs \$O(n+m)\$ work which is less than \$O(nlogm)\$. Yes it's not as "generic" as the template method and won't work for all T. But it doesn't need to be able to do that for the task.

One could solve this using std::unordered_map as well, and the big O time is the same:

template<typename Container>
void findElement(const Container& container, int k){
    std::unordered_map<Container::value_type, int> freq;
    for(auto& value : container){
        freq[value]++;
    }
    auto smallest = freq.end();
    for(auto& entry : freq){
        if(entry.second == k && (smallest != freq.end() || entry.first < smallest.first )){
            smallest = entry;
        }
    }

    if(smallest != freq.end()){
        std::cout << smallest.first <<'\n';
    }
    else{
        std::cerr << "No such element\n";¨
    }
}

The algorithm is essentially the same with one minor difference, the approach with the std::unordered_map may not terminate early on finding the first element with exactly 'k' occurrences as the array based algorithm can. This means that the unordered_map version must visit exactly all 'M<1000' unique values in 'vec' including some overhead from traversing a sparse hash-map, while the array version on average only needs to visit '1000/2' of the possible values.

So they have different cases where they are faster. For example a degenerate case such as K=3 , {999,999,999} is faster with unordered_map as you only visit one unique element but with the array solution you need to (very quickly) scan through the 998 elements in the array. But on average on random sets the array solution is expected to be slightly faster by a constant factor as both have the same big O time.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ The mentioned O(n+m) method is of course the right one, but it has nothing to do with the term 'brute force' (misleading). It is called bucket sort. \$\endgroup\$ – mafu Aug 27 '17 at 16:12
  • \$\begingroup\$ Or one could make 1. just as efficient as the array solution (and support arbitrary sized elements) by using an unordered_map. \$\endgroup\$ – Voo Aug 27 '17 at 20:41
  • \$\begingroup\$ @mafu you are correct, I used the term loosely to refer to the fact of not using any data structure other than plain, fixed size array. \$\endgroup\$ – Emily L. Aug 27 '17 at 21:34
  • \$\begingroup\$ @Voo afaik std::hash<int> isn't required to return the argument unmodified. Which means that you need to compare all elements of the unordered map to find the minimum which prevents the early exit the array solution has. The asymptotic performance is the same but the time constant differs to the advantage of the array solution which also avoids dynamic memory allocations which also take a short time. But no work is less work than some work. Also the task is to solve the programming challenge, not write code for an "enterprise" system. \$\endgroup\$ – Emily L. Aug 27 '17 at 22:24
  • \$\begingroup\$ @Emily You have to iterate through elements in the array to find the first non-0 value, which the dictionary solution can do just the same (it doesn't matter what the hash function is as long as it is reasonably "good" which is trivial for ints). The only difference in performance will be that the dictionary has a relatively more expensive indexing operation. \$\endgroup\$ – Voo Aug 28 '17 at 7:23

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.