Home > Enterprise >  How can I reduce time taken in this c program?
How can I reduce time taken in this c program?

Time:04-13

It's a test on hackerank that asks for the following program. The program takes input, stores it in the dictionary, and checks numerous inputs against this newly created dictionary.

#include <iostream>
#include <map>
using namespace std;

int main()
{
    int create, notPresent;
    string key, value, name;
    map<string, string> phonebook;
    map<string, string>::iterator iter;

    cin >> create;
    for (int i = 0; i < create;   i)
    {
        cin >> key;
        cin >> value;
        phonebook[key] = value;
    }

    while (cin >> name)
    {
        notPresent = 0;
        iter = phonebook.begin();

        while (iter != phonebook.end())
        {
            if (name == iter->first)
                cout << iter->first << "=" << iter->second << endl;
            else
                notPresent  ;
            iter  ;
        }

        if (notPresent == create)
        {
            cout << "Not found" << endl;
        }
    }

    return 0;
}

CodePudding user response:

use map::find instead of manually looping over all entries of dictionary, as it has O(log(n)) complexity instead of O(n) complexity.

CodePudding user response:

Code upgraded!

#include <iostream>
#include <map>
using namespace std;

int main()
{
    unsigned int create, notPresent = 0;
    string key, value, name;
    map<string, string> phonebook;
    cin >> create;

    for (int i = 0; i < create;   i)
    {
        cin >> key;
        cin >> value;
        phonebook[key] = value;
    }

    while (cin >> name)
    {
        auto it = phonebook.find(name);
        if (it == phonebook.end())
            cout << "Not found\n";
        else
            cout << it->first << "=" << it->second << endl;
    }
    return 0;
}
  • Related