Hay infinitas personas de pie en una fila, indexadas desde 1. Una persona que tiene un índice i tiene una fuerza de i 2 . Tienes la fuerza P y la tarea es decir cuál es el número máximo de personas que puedes matar con la fuerza P.
Solo puedes matar a una persona con fuerza X si P ≥ X y después de matarlo, tu fuerza disminuye en X.
Ejemplos:
Entrada: P = 14
Salida: 3
Explicación: La primera persona tendrá fuerza 1 2 = 1 que es < P
P se reduce a 13 después de la primera muerte.
Segunda muerte, P = 13 – 2 2 = 9
Tercera muerte, P = 9 – 3 2 = 0Entrada: P = 58
Salida: 5
Enfoque ingenuo: verifique cada muerte individual comenzando desde 1 hasta que la fuerza P sea mayor o igual a la fuerza de la persona que está siendo asesinada.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción
3
Complejidad de tiempo: O(sqrt(N)), donde N es la fuerza inicial.
Espacio Auxiliar: O(1)
Enfoque eficiente: podemos ver que si matamos a la i -ésima persona, entonces ya hemos matado a (i – 1) a la ésima persona. Esto significa que es una función monótona f cuyo dominio es el conjunto de los números enteros. Ahora podemos aplicar la búsqueda binaria en esta función monótona en la que, en lugar de buscar en una array, buscamos alguna x tal que f(x) sea igual al valor objetivo. La complejidad del tiempo se reduce a O(Log(n)).
A continuación se muestra la implementación del enfoque anterior:
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>
Producción
3
Complejidad de tiempo: O (1000000)
Espacio Auxiliar: O(1000000)
Enfoque más eficiente:
podemos hacer el mismo problema en la complejidad del tiempo O (logn) y la complejidad del espacio en O (1). Comience su búsqueda binaria considerando el valor bajo como 0 y alto como 10^15. Calcularemos el valor medio y, de acuerdo con el medio, cambiaremos la posición de alto y bajo.
A continuación se muestra la implementación del enfoque anterior.
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>
Producción
3
Complejidad de tiempo: O(Log(1000000))
Espacio auxiliar: O(1)