Maximum number of people that can be killed with strength P in C++

Given the task is to find the maximum number of people that can be killed with strength P. Consider a row with infinite people and each of them have an index number starting from 1.

The strength of the s^th person is represented by s². After killing a person with s strength your strength also decreases by s.

Let’s now understand what we have to do using an example −

Input

P = 20

Output

3

Explanation

Strength of 1st person = 1 * 1 = 1 < 20, therefore 1st person can be killed. Remaining strength = P – 1 = 20 – 1 = 19 Strength of 2nd person = 2 * 2 = 4 < 19, therefore 2nd person can be killed. Remaining strength = P – 4 = 19 – 4 = 15 Strength of 3rd person = 3 * 3 = 9 < 15, therefore 3rd person can be killed. Remaining strength = P – 9 = 15 – 9 = 6 Strength of 4th person = 4 * 4 = 16 > 6, therefore 4th person cannot be killed. Output = 3

Input

30

Output

4

Approach used in the below program as follows

• In main() function initialize P = 30 of type int as it will store the strength and pass it into Max() function.

• In Max() function initialize s = 0 and P = 0 both of type int.

• Loop from j = 1 till j * j <= P

• Put s = s + (j * j) and if s <= P add 1 to ans, else break;

• Return ans.

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; int Max(int P){    int s = 0, ans = 0;    for (int j = 1; j * j <= P; j++){       s = s + (j * j);       if (s <= P)          ans++;       else          break;    }    return ans; } //main function int main(){    //Strength    int P = 30;    cout << “Maximum number of people that can be killed with strength P are: ”<<Max(P);    return 0; }

Output

Maximum number of people that can be killed with strength P are: 4