Binary Search giving wrong answer , why ?

Revision en2, by one_piece_22, 2024-09-06 10:07:37

The question was : 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 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;

}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English one_piece_22 2024-09-06 10:09:21 14 Tiny change: 'ion was : \nhttps://' -> 'ion was : Counting Game\nhttps://'
en3 English one_piece_22 2024-09-06 10:08:07 4
en2 English one_piece_22 2024-09-06 10:07:37 11
en1 English one_piece_22 2024-09-06 10:06:34 1484 Initial revision (published)