Smallest subarray with sum greater than a given value | Returns length of smallest subarray with sum greater than x . If there is no subarray with given sum , then returns n + 1 ; Initialize length of smallest subarray as n + 1 ; Pick every element as starting point ; Initialize sum starting with current start ; If first element itself is greater ; Try different ending points for curremt start ; add last element to current sum ; If sum becomes more than x and length of this subarray is smaller than current smallest length , update the smallest length ( or result ) ; Driver Code
< ? php function smallestSubWithSum ( $ arr , $ n , $ x ) { $ min_len = $ n + 1 ; for ( $ start = 0 ; $ start < $ n ; $ start ++ ) { $ curr_sum = $ arr [ $ start ] ; if ( $ curr_sum > $ x ) return 1 ; for ( $ end = $ start + 1 ; $ end < $ n ; $ end ++ ) { $ curr_sum += $ arr [ $ end ] ; if ( $ curr_sum > $ x && ( $ end - $ start + 1 ) < $ min_len ) $ min_len = ( $ end - $ start + 1 ) ; } } return $ min_len ; } $ arr1 = array ( 1 , 4 , 45 , 6 , 10 , 19 ) ; $ x = 51 ; $ n1 = sizeof ( $ arr1 ) ; $ res1 = smallestSubWithSum ( $ arr1 , $ n1 , $ x ) ; if ( ( $ res1 == $ n1 + 1 ) == true ) echo " Not ▁ possible STRNEWLINE " ; else echo $ res1 , " STRNEWLINE " ; $ arr2 = array ( 1 , 10 , 5 , 2 , 7 ) ; $ n2 = sizeof ( $ arr2 ) ; $ x = 9 ; $ res2 = smallestSubWithSum ( $ arr2 , $ n2 , $ x ) ; if ( ( $ res2 == $ n2 + 1 ) == true ) echo " Not ▁ possible STRNEWLINE " ; else echo $ res2 , " STRNEWLINE " ; $ arr3 = array ( 1 , 11 , 100 , 1 , 0 , 200 , 3 , 2 , 1 , 250 ) ; $ n3 = sizeof ( $ arr3 ) ; $ x = 280 ; $ res3 = smallestSubWithSum ( $ arr3 , $ n3 , $ x ) ; if ( ( $ res3 == $ n3 + 1 ) == true ) echo " Not ▁ possible STRNEWLINE " ; else echo $ res3 , " STRNEWLINE " ; ? >