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

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;
}
}
}
}
• Note that you can arrive at much the same process as proposed in Dean Menezes' answer if you process the qs in ascending order, advancing to the next q at each "print" (you have to do something about the order of actual output) - see Mark H's comment, too. Oct 15, 2022 at 6:26
• And you might do better than both, if you do that, and binary-search from one q to the next (reducing the search space each iteration). Oct 15, 2022 at 12:09

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;
}
}
• binary search in n elements needs log n time. Oct 15, 2022 at 0:39
• Two suggestions: 1) Use std::distance instead of pointer subtraction to get ans (it amounts to the same thing, but the named function is more readily understood). 2) Sort the list of target numbers (the qs) in descending order and use the lower_bound found in each search to limit the search for the next q. Oct 15, 2022 at 2:46
• I think the binary search solution takes $O(q \log n)$ time, because it does q times a binary search in n elements. Oct 15, 2022 at 10:22

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\$$.

• The remark about using namespace doesn't mention what's wrong with it, and doesn't offer alternatives. I think this is very poor guidance, especially for a new user. Oct 15, 2022 at 10:31
• @janos: True. If you feel like adding appropriate guidance, again, go ahead. I didn't. Oct 15, 2022 at 10:32
• The other thing that seems common in "coding competition" questions is a complete trust in inputs, with no checking the state of std::cin before using the value that may not have been read correctly. Oct 15, 2022 at 12:07
• I would like to count on experienced programmers to give appropriate guidance, to nurture future generations of better programmers and software. Posting my own answer every time doesn't scale. Oct 15, 2022 at 20:01