Length of Smallest subarray in range 1 to N with sum greater than a given value | C ++ implementation of the above approach . ; Function to do a binary search on a given range . ; Total sum is the sum of N numbers . ; Sum until mid ; If remaining sum is < the required value , then the required number is in the right half ; Driver code
#include <iostream> NEW_LINE using namespace std ; int usingBinarySearch ( int start , int end , int N , int S ) { if ( start >= end ) return start ; int mid = start + ( end - start ) / 2 ; int totalSum = ( N * ( N + 1 ) ) / 2 ; int midSum = ( mid * ( mid + 1 ) ) / 2 ; if ( ( totalSum - midSum ) <= S ) { return usingBinarySearch ( start , mid , N , S ) ; } return usingBinarySearch ( mid + 1 , end , N , S ) ; } int main ( ) { int N , S ; N = 5 ; S = 11 ; cout << ( N - usingBinarySearch ( 1 , N , N , S ) + 1 ) << endl ; return 0 ; }