Longest subarray having sum K | Set 2 | C ++ program for the above approach ; To store the prefix sum array ; Function for searching the lower bound of the subarray ; Iterate until low less than equal to high ; For each mid finding sum of sub array less than or equal to k ; Return the final answer ; Function to find the length of subarray with sum K ; Initialize sum to 0 ; Push the prefix sum of the array arr [ ] in prefix [ ] ; Search r for each i ; Update ans ; Print the length of subarray found in the array ; Driver Code ; Given array arr [ ] ; Given sum K ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > v ; int bin ( int val , int k , int n ) { int lo = 0 ; int hi = n ; int mid ; int ans = -1 ; while ( lo <= hi ) { mid = lo + ( hi - lo ) / 2 ; if ( v [ mid ] - val <= k ) { lo = mid + 1 ; ans = mid ; } else hi = mid - 1 ; } return ans ; } void findSubarraySumK ( int arr [ ] , int N , int K ) { int sum = 0 ; v . push_back ( 0 ) ; for ( int i = 0 ; i < N ; i ++ ) { sum += arr [ i ] ; v . push_back ( sum ) ; } int l = 0 , ans = 0 , r ; for ( int i = 0 ; i < N ; i ++ ) { r = bin ( v [ i ] , K , N ) ; ans = max ( ans , r - i ) ; } cout << ans ; } int main ( ) { int arr [ ] = { 6 , 8 , 14 , 9 , 4 , 11 , 10 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int K = 13 ; findSubarraySumK ( arr , N , K ) ; return 0 ; }