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;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
``` class Solution { public: long long getCount(int n, vector &arr, int a, int b) { long long ans = 0;
} };```
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.