CODEWITHSUNDEEP
c++algorithm
user1692342
user1692342

Reputation: 5237

Get Number of groups which have same frequency of digits in a given set of numbers

This is a question I had got in an interview and I was wondering what the best approach would be. A list of numbers is given and we need to identify the number of groups in which the digits of each number have same frequency and print the groups. For example: For example if numbers are: 1 10 3 33

There are 4 groups:

G1={1}has one 1. 
G2={3} has one 3. 
G3={10}has one 1 and one 0. 
G4={33}as two 3s.

I was thinking of keeping a vector of maps. The maps will contain a frequency of each digit. Now when a number comes check in the entire vector if there exists an entry which will have a same frequency map of the current number. If it exists append to a list. I am not able to identify how i should identify the groups as well to print it. Is there a better way to solve this problem as I feel my solution is really inefficient.

Upvotes: 2

Views: 437

Answers (2)

fjardon
fjardon

Reputation: 7996

Think about how hash-table works. You apply a hash function to the item and based on this hash value you assign the item to a slot. But it may happen that two different items have the same hash value. In that case the hash-table will create a list of the values with the same hash. This is called a collision.

In a hash-table implementation we try to avoid collision. But here it will serve you well. If you can find a hash function such that: two numbers in the same group have the same hash value, you could easily group the numbers.

An example of such a hash function is this:

  • convert the number to a string
  • sort the string by ascending order

All numbers in the same group will have the same hash value.

Example implementation:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <sstream>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;


unordered_map<string, vector<int>> group_numbers(vector<int> numbers) {
    unordered_map<string, vector<int>> results;
    for(auto n : numbers) {
        stringstream buffer;
        buffer << n;
        string hash;
        buffer >> hash;

        sort(begin(hash), end(hash));
        results[hash].push_back(n);
    }
    return results;
}


int main() {
    vector<int> numbers{1, 10, 3, 33, 133, 331, 313, 333};
    auto results = group_numbers(numbers);
    int group = 0;
    for(auto kv : results) {
        cout << "Group " << (++group) << " : ";
        copy(begin(kv.second), end(kv.second),
             ostream_iterator<int>(cout, " "));
        cout << "\n";
    }
}

Then when run it prints:

Group 1 : 333
Group 2 : 133 331 313
Group 3 : 1
Group 4 : 10
Group 5 : 33
Group 6 : 3

Upvotes: 2

Khalil Khalaf
Khalil Khalaf

Reputation: 9407

So if I understood the question right, they didn't care about the actual numbers. They are just asking about the frequency. Therefore, this will provide us with a std::map<int,int> where key is the whole number from the list and value is the frequency of the numbers in that key. We only need to display categories as whatever has value of 1, 2, 3.. or maybe check which has equal value etc. 

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

int main()
{
    std::vector<int> MyVec = { 1, 10, 3, 33 }; // sample data
    std::map<int, int> MyMap;

    for (int i = 0; i < MyVec.size(); i++) // fill the map with ALL the numbers first
        MyMap[MyVec[i]]++;

    for (auto itr = MyMap.begin(); itr != MyMap.end(); itr++) // increment each value based on the frequence of the digits found in the key
    {
        if (itr->first < 10) // it has one
            continue;
        else
        {
            int temp = itr->first;
            while (temp >= 10)
            {
                temp = temp % 10;
                itr->second++;
            }
        }
    }

    for (auto itr = MyMap.begin(); itr != MyMap.end(); itr++) // display
    {
        std::cout << "first: " << itr->first << " second: " << itr->second << "\n";
    }

    return 0;
}

Upvotes: 0

Related Questions