The question was : Counting Game https://practice.geeksforgeeks.org/contest/gfg-weekly-167-rated-contest/problems
Can you Please help to find out why the binary search is giving wrong answer !
In this question all the elements are positive !
NOTE: single element should always be counted whether it lies or not in [a,b] range
long long fun( int n, int a , int b , vector&arr ){
vector<ll> pre(n+1);
for(int i = 1; i <= n; i++) pre[i] = pre[i-1]+arr[i-1];
ll ans = n;
for(int i = 1; i <= n; i++ ){
ll low = i; ll high = n; ll lb= -1;
while(low <= high){
int mid = (low+high)/2;
if( pre[mid]-pre[i-1] >= a ){
if(pre[mid]-pre[i-1] <= b) lb = mid;
high = mid-1;
}
else low = mid+1;
}
low = i; high = n; ll rb = -1;
while( low <= high ){
int mid = (low+high)/2;
if( pre[mid]-pre[i-1] <= b ){
if( pre[mid]-pre[i-1] >= a ) rb = mid;
low = mid+1;
}
else high = mid-1;
}
if( rb != -1 && lb != -1 ) {
ans += rb-lb+1;
if( lb == i && rb != -1 )ans--;
}
}
return ans;}
use multiset to find 2 max and 2 min elements in a sliding window.
Ok , Thanks !
Sir, can you please help to find error in this code of above question
~~~~~~~~~~~~~~~~~~~ //this is the code
multisetmst; int i = 0; int j = 0; int ans = 0;
while( j < n ){ mst.insert(arr[j]); if(mst.size()==1){ ans += j-i+1; j++; continue; } auto it = --mst.end(); int max1 = *(it); int max2 = *(--it); int min1 = *(mst.begin()); int min2 = *(++mst.begin()); while( max1+max2 > b || min2+min1 < a ){ mst.erase(mst.find(arr[i])); i++; if(mst.size()==1)break; auto it = --mst.end(); int max1 = *(it); int max2 = *(--it); int min1 = *(mst.begin()); int min2 = *(++mst.begin()); } ans += j-i+1; j++; } return ans;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
``` class Solution { public: long long getCount(int n, vector &arr, int a, int b) { long long ans = 0;
multiset<int> st; for (int i = 0, j = 0; j < n; j++) { st.insert(arr[j]); while (j - i + 1 > 1) { int x = *st.begin() + *(++st.begin()); int y = *st.rbegin() + *(++st.rbegin()); if (x >= a && y <= b) break; st.erase(st.find(arr[i])); i++; } ans += j - i + 1; } return ans;} };```
Check that lb and rb are accurately calculated and lb is always less than or equal to rb. Make sure you're not double-counting or missing valid subarrays.