Maximum number of people that can be killed with strength P | Javascript 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
const kN = 1000000 ; function maxPeople ( p ) { let sums = new Array ( kN ) ; sums [ 0 ] = 0 ; for ( let i = 1 ; i < kN ; i ++ ) sums [ i ] = ( i * i ) + sums [ i - 1 ] ; let it = lower_bound ( sums , 0 , kN , p ) ; if ( it > p ) { -- it ; } return it ; } function lower_bound ( a , low , high , element ) { while ( low < high ) { let middle = low + parseInt ( ( high - low ) / 2 ) ; if ( element > a [ middle ] ) low = middle + 1 ; else high = middle ; } return low ; } let p = 14 ; document . write ( maxPeople ( p ) ) ;