CODEWITHSUNDEEP
c++sortingdata-structuresimplementationarray-algorithms
Abhi Gupta
Abhi Gupta

Reputation: 17

How can i optimize this below program?

You are given an array A of length N. For any given integer X, you need to find an integer Z strictly greater than X such that Z is not present in the array A. You need to minimize the value of Z.

INPUT:

First line : Two space seperated integers N and Q denoting the number of elements in array A and the number of queries respectively

Second line: N space seperated integers denoting the array elements

Next Q lines: Each line consists of an integer X

OUTPUT: Print Q lines, each line denoting the answer to the corresponding query.

Sample Input:

5 2
2 7 5 9 15
3
9

Sample output:

4
10

Source - https://www.hackerearth.com/practice/algorithms/sorting/quick-sort/practice-problems/algorithm/yet-to-keep-6f89250c/description/

My solution-

int main()
{
    ll n,q;
    cin>>n>>q;
    map<ll,bool>mp;
    for(ll i=0;i<n;i++)
    {
        ll x;
        cin>>x;
        mp[x]=true;
    }
    while(q--)
    {
        ll x;
        cin>>x;
        x++;
        while(mp[x])
        {
            x++;
        }
        cout<<x<<endl;
    }
}

Upvotes: 1

Views: 131

Answers (1)

Jarod42
Jarod42

Reputation: 217145

Your complexity by query is O(n)*(Z-X),

you might already reduce to O(n)+(Z-X) with:

ll x;
std::cin >> x;
x++;
auto it = mp.find(x);
if (it != mp.end()) {
    while (it != mp.end() && it->first == x) {
        ++it;
        ++x;
    }
}
std::cout << x << std::endl;

But I think that building intervals in pre-processing would allow even better performance (O(log(Intervals))).

Upvotes: 3

Related Questions