Maximum number of people that can be killed with strength P

0 0 10 minutes read

There are infinite people standing in a row, indexed from 1. A person having index i has strength of i². You have strength P and the task is to tell what is the maximum number of people you can kill with strength P.
You can only kill a person with strength X if P ? X and after killing him, your strength decreases by X.

Examples:

Input: P = 14
Output: 3
Explanation: First person will have strength 1² = 1 which is < P
P gets reduced to 13 after the first kill.
Second kill, P = 13 – 2² = 9
Third kill, P = 9 – 3² = 0

Input: P = 58
Output: 5

Naive approach: Check every single kill starting from 1 until the strength P is greater than or equal to the strength of the person being killed.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum number of people that can
// be killed
int maxPeople(int p)
{
    int tmp = 0, count = 0;
 
    // Loop will break when the ith person cannot be killed
    for (int i = 1; i * i <= p; i++) {
        tmp = tmp + (i * i);
        if (tmp <= p)
            count++;
        else
            break;
    }
    return count;
}
 
// Driver code
int main()
{
    int p = 14;
    cout << maxPeople(p);
 
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

C

// C implementation of the approach
#include <stdio.h>
 
// Function to return the maximum number of people that can
// be killed
int maxPeople(int p)
{
    int tmp = 0, count = 0;
 
    // Loop will break when the ith person cannot be killed
    for (int i = 1; i * i <= p; i++) {
        tmp = tmp + (i * i);
        if (tmp <= p)
            count++;
        else
            break;
    }
    return count;
}
 
// Driver code
int main()
{
    int p = 14;
    printf("%d", maxPeople(p));
 
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Java

// Java implementation of the approach
import java.util.*;
 
class GFG {
    // Function to return the maximum number of people that
    // can be killed
    static int maxPeople(int p)
    {
        int tmp = 0, count = 0;
 
        // Loop will break when the ith person cannot be
        // killed
        for (int i = 1; i * i <= p; i++) {
            tmp = tmp + (i * i);
            if (tmp <= p)
                count++;
            else
                break;
        }
        return count;
    }
 
    // Driver code
    public static void main(String args[])
    {
        int p = 14;
        System.out.println(maxPeople(p));
    }
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Python3

# Python3 implementation of the approach 
 
from math import sqrt
 
# Function to return the maximum 
# number of people that can be killed 
def maxPeople(p) : 
     
    tmp = 0; count = 0; 
 
    # Loop will break when the ith person 
    # cannot be killed 
    for i in range(1, int(sqrt(p)) + 1) :
        tmp = tmp + (i * i); 
        if (tmp <= p) :
            count += 1; 
        else :
            break; 
     
    return count; 
 
 
# Driver code 
if __name__ == "__main__" : 
 
    p = 14; 
    print(maxPeople(p)); 
     
# This code is contributed by AnkitRai01

C#

// C# implementation of the approach
using System;
 
class GFG
{ 
     
// Function to return the maximum
// number of people that can be killed
static int maxPeople(int p)
{
    int tmp = 0, count = 0;
 
    // Loop will break when the ith person
    // cannot be killed
    for (int i = 1; i * i <= p; i++) 
    {
        tmp = tmp + (i * i);
        if (tmp <= p)
            count++;
        else
            break;
    }
    return count;
}
 
// Driver code
public static void Main()
{
    int p = 14;
    Console.WriteLine(maxPeople(p));
}
}
 
// This code is contributed by anuj_67..

Javascript

<script>
 
// javascript implementation of the approach
   
// Function to return the maximum
// number of people that can be killed
function maxPeople(p)
{
    var tmp = 0, count = 0;
 
    // Loop will break when the ith person
    // cannot be killed
    for (var i = 1; i * i <= p; i++) 
    {
        tmp = tmp + (i * i);
        if (tmp <= p)
            count++;
        else
            break;
    }
    return count;
}
 
// Driver code
 
var p = 14;
document.write(maxPeople(p));
 
// This code is contributed by Amit Katiyar 
 
</script>

Output

Time Complexity: O(sqrt(N)), where N is the initial strength.
Auxiliary Space: O(1)

Efficient approach: We can see if we kill i^th person then we have already killed (i – 1)^th person. This means it is a monotonic function f whose domain is the set of integers. Now we can apply binary search on this monotonic function in which instead of array lookup we are now looking for some x such that f(x) is equal to the target value. Time complexity reduces to O(Log(n)).

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
static constexpr int kN = 1000000;
 
// Function to return the maximum
// number of people that can be killed
int maxPeople(int p)
{
    // Storing the sum beforehand so that
    // it can be used in each query
    ll sums[kN];
    sums[0] = 0;
    for (int i = 1; i < kN; i++)
        sums[i] = (ll)(i * i) + sums[i - 1];
 
    // lower_bound returns an iterator pointing to the
    // first element greater than or equal to your val
    auto it = std::lower_bound(sums, sums + kN, p);
    if (*it > p) {
 
        // Previous value
        --it;
    }
 
    // Returns the index in array upto which
    // killing is possible with strength P
    return (it - sums);
}
 
// Driver code
int main()
{
    int p = 14;
    cout << maxPeople(p);
 
    return 0;
}

Java

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

Python3

# Python3 implementation of the approach
kN = 1000000;
 
# Function to return the maximum
# number of people that can be killed
def maxPeople(p):
 
    # Storing the sum beforehand so that
    # it can be used in each query
    sums = [0] * kN;
    sums[0] = 0;
    for i in range(1, kN):
        sums[i] = (i * i) + sums[i - 1];
 
    # lower_bound returns an iterator 
    # pointing to the first element 
    # greater than or equal to your val
    it = lower_bound(sums, 0, kN, p);
    if (it > p):
 
        # Previous value
        it -= 1;
 
    # Returns the index in array upto which
    # killing is possible with strength P
    return it;
 
def lower_bound(a, low, high, element):
    while(low < high):
        middle = int(low + (high - low) / 2);
        if(element > a[middle]):
            low = middle + 1;
        else:
            high = middle;
    return low;
 
# Driver code
if __name__ == '__main__':
    p = 14;
    print(maxPeople(p));
 
# This code contributed by Rajput-Ji

C#

// C# implementation of the approach
using System;     
     
public class GFG
{
 
static int kN = 1000000;
 
// Function to return the maximum
// number of people that can be killed
static int maxPeople(int p)
{
    // Storing the sum beforehand so that
    // it can be used in each query
    long []sums = new long[kN];
    sums[0] = 0;
    for (int i = 1; i < kN; i++)
        sums[i] = (long)(i * i) + sums[i - 1];
 
    // lower_bound returns an iterator pointing to the
    // first element greater than or equal to your val
    int it = lower_bound(sums, 0, kN, p);
    if (it > p) 
    {
 
        // Previous value
        --it;
    }
 
    // Returns the index in array upto which
    // killing is possible with strength P
    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;
}
 
// Driver code
public static void Main(String[] args)
{
    int p = 14;
    Console.WriteLine(maxPeople(p));
}
}
 
// This code has been contributed by 29AjayKumar

Javascript

<script>
// Javascript implementation of the approach
 
const kN = 1000000;
 
// Function to return the maximum
// number of people that can be killed
function maxPeople(p)
{
    // Storing the sum beforehand so that
    // it can be used in each query
    let sums = new Array(kN);
    sums[0] = 0;
    for (let i = 1; i < kN; i++)
        sums[i] = (i * i) + sums[i - 1];
 
    // lower_bound returns an iterator pointing to the
    // first element greater than or equal to your val
    let it = lower_bound(sums, 0, kN, p);
    if (it > p) {
 
        // Previous value
        --it;
    }
 
    // Returns the index in array upto which
    // killing is possible with strength P
    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;
}
 
// Driver code
    let p = 14;
    document.write(maxPeople(p));
 
</script>

Output

Time Complexity: O(1000000)

Auxiliary Space: O(1000000)

More Efficient Approach :
We can do the same problem in time complexity O(logn) and Space Complexity in O(1). Start your binary search by considering the value of low as 0 and high as 10^15. We will calculate the mid-value and according to mid, we will change the position of low and high.

Below is the implementation of the above approach.

C++

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

Java

// Java implementation of the approach
class GFG{
     
// Helper function which returns the sum
// of series (1^2 + 2^2 +...+ n^2)
static long squareSeries(long n)
{
    return(n * (n + 1) * (2 * n + 1)) / 6;
}
 
// maxPeople function which returns
// appropriate value using Binary Search
// in O(logn)
static long maxPeople(long n)
{
     
    // Set the lower and higher values
    long low = 0;
    long high = 1000000L;
    long ans = 0L;
     
    while (low <= high)
    {
         
        // Calculate the mid using
        // low and high
        long mid = low + ((high - low) / 2);
        long value = squareSeries(mid);
 
        // Compare value with n
        if (value <= n)
        {
            ans = mid;
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
     
    // Return the ans
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    long p = 14;
     
    System.out.println(maxPeople(p));
}}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 implementation of the approach
 
# helper function which returns the sum
# of series (1^2 + 2^2 +...+ n^2)
def squareSeries(n):
    return (n*(n+1)*(2*n+1))//6
 
# maxPeople function which returns
# appropriate value using Binary Search
# in O(logn)
 
def maxPeople(n):
 
    # Set the lower and higher values
    low = 0
    high = 1000000000000000
    while low<=high:
 
        # calculate the mid using
        # low and high
 
        mid = low + ((high-low)//2)
        value = squareSeries(mid)
 
        #compare value with n
        if value<=n:
            ans = mid
            low = mid+1
        else:
            high = mid-1
 
    # return the ans
    return ans
 
if __name__=='__main__':
    p=14
    print(maxPeople(p))
 
# This code is contributed bu chaudhary_19
# (* Mayank Chaudhary)

C#

// C# implementation of the approach
using System;
 
class GFG{
     
// Helper function which returns the sum
// of series (1^2 + 2^2 +...+ n^2)
static long squareSeries(long n)
{
    return(n * (n + 1) * (2 * n + 1)) / 6;
}
 
// maxPeople function which returns
// appropriate value using Binary Search
// in O(logn)
static long maxPeople(long n)
{
     
    // Set the lower and higher values
    long low = 0;
    long high = 1000000L;
    long ans = 0L;
     
    while (low <= high)
    {
         
        // Calculate the mid using
        // low and high
        long mid = low + ((high - low) / 2);
        long value = squareSeries(mid);
 
        // Compare value with n
        if (value <= n)
        {
            ans = mid;
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
     
    // Return the ans
    return ans;
}
 
// Driver code
public static void Main(String[] args)
{
    long p = 14;
     
    Console.Write(maxPeople(p));
}}
 
// This code is contributed by shivanisinghss2110

Javascript

<script>
// Javascript implementation of the approach
 
// Helper function which returns the sum
// of series (1^2 + 2^2 +...+ n^2)
function squareSeries(n)
{
    return Math.floor((n * (n + 1) * (2 * n + 1)) / 6);
}
 
// maxPeople function which returns
// appropriate value using Binary Search
// in O(logn)
function maxPeople(n)
{
 
    // Set the lower and higher values
    let low = 0;
    let high = 1000000;
    let ans = 0;
      
    while (low <= high)
    {
          
        // Calculate the mid using
        // low and high
        let mid = low + Math.floor((high - low) / 2);
        let value = squareSeries(mid);
  
        // Compare value with n
        if (value <= n)
        {
            ans = mid;
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
      
    // Return the ans
    return ans;
}
 
// Driver code
let p = 14;
 
document.write(maxPeople(p));
 
// This code is contributed by avanitrachhadiya2155
</script>

Output

Time Complexity: O(Log(1000000))
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!