Solution
Brute Force approach:
We can take values from 0 to max(array A) for L. After fixing the value of L, we simply calculate the scores of both arrays and find the maximum difference.
After iterating on all values of L, we can print the final scores.
Time complexity of this approach is O(|max(array A)| * |max(N, M)|). It is clear from the constraints that this approach is very inefficient.
Let us now look at efficient approaches to this problem.
Efficient approach:
We don’t need to check for every value in [0, max(array A)] as L. Instead, we take L as elements in array A.
For calculating the scores efficiently, we use binary search. Here 2 points are contributed for every element which is less than L and +3 for elements greater than equal to L. We sort both arrays.
For every element in A, where A[i] is set as L, we find scores of both the array.
For array A, elements before the current element will contribute +2, and elements after the current element will contribute +3.
For array B, we find the first index, greater than equal to L, and then similar to array A, elements after this index contributes +3 and elements before a +2 in the score.
After iterating over the whole array A, we print the final scores of A and B.
Program
#include <bits/stdc++.h>
using namespace std;
void solve(){
int tt;
// number of test cases.
cin >> tt;
while(tt--){
// taking inputs.
int n;cin >> n;
vector<int>a(n+1);
for(int i=0; i<n; i++)cin >> a[i];
a[n++] = INT_MAX;
int m;cin >> m;
vector<int>b(m);
for(int i=0; i<m; i++)cin >> b[i];
// sort the arrays.
sort(a.begin(), a.end());
sort(b.begin(), b.end());
// find the optimal L.
int p=0, q=0;
int diff = INT_MIN;
for(int i=0; i<n; i++){
int L = a[i];
int scoreA = 2*i + 3*(n-i-1);
int idxB = lower_bound(b.begin(), b.end(), L) - b.begin();
// int idxB = upper_bound(b.begin(), b.end(), L-1) - b.begin();
int scoreB = 2*idxB + 3*(m - idxB);
// update when you find a new optimal L.
if(scoreA-scoreB > diff){
// take account of the new optimal difference.
diff = scoreA -scoreB;
p = scoreA;
q = scoreB;
}
}
// print the answers.
cout << p << ":" << q << endl;
}
}
int main(){
// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
solve();
return 0;
}
INPUT
2
3
1 2 3
2
5 6
5
6 7 8 9 10
5
1 2 3 4 5
OUTPUT
9:6
15:10
Time Complexity
Sorting takes O(n*log(n)). Binary search is used when iterating over array A. The time complexity of lower_bound is O(log(m)).
The overall time complexity of the program is O(N*(log(M) + log(N))).
Space Complexity
The auxiliary space complexity of the program is O(1).
FAQs
Q1). Explain the lower_bound() function in C++?
This function returns an iterator pointing to the first element in the container, which is greater than equal to the value.
Q2). Explain the upper_bound() function in C++?
This function returns an iterator pointing to the first element in the container, which is greater than the value.
Q3). What is the time complexity of lower_bound() & upper_bound() functions in C++?
The time complexity of lower_bound & upper_bound is O(log(N)).
Q4). What is the underlying algorithm of sort() function in C++?
The sort() function uses IntroSort. IntroSort is a hybrid sorting technique that uses Quicksort, Heapsort, and Insertionsort to minimize the running time.
Key Takeaways
Cheers if you reached here!!
The purpose of this article was to discuss an intriguing problem using arrays and sorting. Array-based problems are sometimes simple to implement, but finding an efficient approach remains a difficulty.
Yet learning never stops, and there is a lot more to learn. So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Learning!!
38+ registered 