Longest subarray having sum K | Set 2 | To store the prefix sum1 array ; Function for searching the lower bound of the subarray ; Iterate until low less than equal to high ; For each mid finding sum1 of sub array less than or equal to k ; Return the final answer ; Function to find the length of subarray with sum1 K ; Initialize sum1 to 0 ; Push the prefix sum1 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 sum1 K ; Function Call
v = [ ] NEW_LINE def bin1 ( val , k , n ) : NEW_LINE INDENT global v NEW_LINE lo = 0 NEW_LINE hi = n NEW_LINE mid = 0 NEW_LINE ans = - 1 NEW_LINE while ( lo <= hi ) : NEW_LINE INDENT mid = lo + ( ( hi - lo ) // 2 ) NEW_LINE if ( v [ mid ] - val <= k ) : NEW_LINE INDENT lo = mid + 1 NEW_LINE ans = mid NEW_LINE DEDENT else : NEW_LINE INDENT hi = mid - 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT def findSubarraysum1K ( arr , N , K ) : NEW_LINE INDENT global v NEW_LINE sum1 = 0 NEW_LINE v . append ( 0 ) NEW_LINE for i in range ( N ) : NEW_LINE INDENT sum1 += arr [ i ] NEW_LINE v . append ( sum1 ) NEW_LINE DEDENT l = 0 NEW_LINE ans = 0 NEW_LINE r = 0 NEW_LINE for i in range ( len ( v ) ) : NEW_LINE INDENT r = bin1 ( v [ i ] , K , N ) NEW_LINE ans = max ( ans , r - i ) NEW_LINE DEDENT print ( ans ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 6 , 8 , 14 , 9 , 4 , 11 , 10 ] NEW_LINE N = len ( arr ) NEW_LINE K = 13 NEW_LINE findSubarraysum1K ( arr , N , K ) NEW_LINE DEDENT