Maximum number of people that can be killed with strength P | C ++ implementation of the approach ; Helper function which returns the sum of series ( 1 ^ 2 + 2 ^ 2 + ... + n ^ 2 ) ; maxPeople function which returns appropriate value using Binary Search in O ( logn ) ; Set the lower and higher values ; Calculate the mid using low and high ; Compare value with n ; Return the ans ; Driver code
#include <algorithm> NEW_LINE #include <bits/stdc++.h> NEW_LINE using namespace std ; long squareSeries ( long n ) { return ( n * ( n + 1 ) * ( 2 * n + 1 ) ) / 6 ; } long maxPeople ( long n ) { long low = 0 ; long high = 1000000L ; long ans = 0L ; while ( low <= high ) { long mid = low + ( ( high - low ) / 2 ) ; long value = squareSeries ( mid ) ; if ( value <= n ) { ans = mid ; low = mid + 1 ; } else { high = mid - 1 ; } } return ans ; } int main ( ) { long p = 14 ; cout << maxPeople ( p ) ; return 0 ; }