Print the count of input numbers less than each of mutiple values "q"

Question

I was solving a question in a competition I joined that asked for a program that calculates how many numbers are less than \$q\$. I solved the question but didn't get the full mark because the code was too slow.

The input is 4 lines, the 1st contains \$n\$ (the length of the array), the second contains the elements of the array, the third contains how many numbers it wants the program to find out how many numbers are less than it and the fourth line contains the numbers.

I remember some of the variables can be as big as \$10^9\$.

the output is the number of numbers less than q with a space after it. there can be multiple "\$q\$"s.

here is the code I entered during the competition:

#include <iostream>

using namespace std;

int main()
{
   int n,Q;
   cin>>n;
   int x[n];
   for(int i=0;i<n;i++){
       cin>>x[i];
   }
   cin>>Q;
   for(int i=0;i<Q;i++){
       int q,count=0;
       cin>>q;
       for(int j=0;j<n;j++){
           if(q>x[j]){
               count++;
           }
       }
       cout<<count<<' ';
   }
}

I have qualified for the next round and decided to revisit the question as revision so I came up with this code, unfortunately I don't know how to test how fast it is:

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n,Q,q;
    cin>>n;
    int x[n];
    for(int i=0;i<n;i++){
        cin>>x[i];
    }
    sort(x,x+n);
    cin>>Q;
    for(int i=0;i<Q;i++){
        cin>>q;
        for(int j=0;j<n;j++){
            if(q<=x[j]){
                cout<<j<<' ';
                j+=n;
                }
        }
    }
}

Answer 1

Stylistically you should change j += n to a break for exiting the loop and make the query variable local.

#include <iostream>
using namespace std;

int main()
{
    int n,Q;
    cin>>n;
    int x[n];
    for(int i=0;i<n;i++){
        cin>>x[i];
    }
    sort(x,x+n);
    cin>>Q;
    for(int i=0;i<Q;i++){
        int q; cin>>q;
        for(int j=0;j<n;j++){
            if(q<=x[j]){
                cout<<j<<' ';
                break;
                }
        }
    }
}

Your code is still \$O(n*q)\$ since it may still read every element of the array.

It is better to use binary search, which takes logarithmic time.

It now takes \$O(n \log n + q \log n)\$ time.

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

int main()
{
    int n,Q;
    cin>>n;
    int x[n];
    for(auto &num : x)
        cin>>num;
    
    sort(x,x+n);
    cin>>Q;
    for(int i=0;i<Q;i++){
        int q; cin>>q;
        /* get the index of the first number that is not less than q, or n if none exists */
        int ans = lower_bound(x, x+n, q) - x;
        cout << ans << endl; 
    }
}

Answer 2

One thing not yet said often enough about using namespace std;:
It's a crying shame to encourage adverse habits, no less so for a "coding competition" site.

There is one inconsistently indented closing brace in the revised code.

Neither revision documents the purpose of the code.

---

Assuming the number \$Q\$ of \$q\$s much lower than \$n\$, a different approach holds promise to be faster:

let limits be an ordered copy of the \$q\$s
initialise a counter for each limit to zero
for each of \$n\$ numbers,
    increment the counter of the lowest limit not exceeding it by one
replace the counter values by the prefix sum
for each \$q\$,
    look up and print the count

Note that while this looks O(\$n\$ log \$Q\$), that's the same as O(\$n\$ log \$n\$) for any given fixed ratio \$Q/n\$.