Maximum number of people that can be killed with strength P | Java implementation of the approach ; Function to return the maximum number of people that can be killed ; Storing the sum beforehand so that it can be used in each query ; lower_bound returns an iterator pointing to the first element greater than or equal to your val ; Previous value ; Returns the index in array upto which killing is possible with strength P ; Driver code
class GFG { static int kN = 1000000 ; static int maxPeople ( int p ) { long [ ] sums = new long [ kN ] ; sums [ 0 ] = 0 ; for ( int i = 1 ; i < kN ; i ++ ) sums [ i ] = ( long ) ( i * i ) + sums [ i - 1 ] ; int it = lower_bound ( sums , 0 , kN , p ) ; if ( sums [ it ] > p ) { -- it ; } return it ; } private static int lower_bound ( long [ ] a , int low , int high , int element ) { while ( low < high ) { int middle = low + ( high - low ) / 2 ; if ( element > a [ middle ] ) low = middle + 1 ; else high = middle ; } return low ; } public static void main ( String [ ] args ) { int p = 14 ; System . out . println ( maxPeople ( p ) ) ; } }