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;
}
i think you understood the problem wrong. What your code does is.... it checks if some prefix of arr[i...] has sum >= a and some suffix of arr[i...] has sum <= b,
But the problem is asking for subarrays in which sum of any 2 elements lies in the range [a, b]
for any subarray to be valid: (sum of 2 minimum elements) >= a and (sum of 2 maximums elements) <= b
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.