Dadas las constantes de la ecuación cuadrática F(x) = Ax 2 + Bx + C como A, B y C y un número entero K , la tarea es encontrar el valor más pequeño de la raíz x tal que F(x) ≥ K y x > 0 . Si no existen tales valores, imprima «-1» . Se da que F(x) es una función monótonamente creciente.
Ejemplos:
Entrada: A = 3, B = 4, C = 5, K = 6
Salida: 1
Explicación:
Para los valores dados F(x) = 3x 2 + 4x + 5 el valor mínimo de x es 1, F(x) = 12, que es mayor que el valor dado de K .Entrada: A = 3, B = 4, C = 5, K = 150
Salida: 7
Explicación:
Para los valores dados F(x) = 3x 2 + 4x + 5 el valor mínimo de x es 7, F(x) = 180, que es mayor que el valor dado de K .
Enfoque: La idea es utilizar la búsqueda binaria para encontrar el valor mínimo de x . A continuación se muestran los pasos:
- Para obtener el valor igual o mayor que K, el valor de x debe estar en el rango [1, sqrt(K)] ya que esta es una ecuación cuadrática.
- Ahora, básicamente existe la necesidad de buscar el elemento apropiado en el rango, por lo que se implementa esta búsqueda binaria.
- Cálculo de F(mid) , donde mid es el valor medio del rango [1, sqrt(K)] . Ahora son posibles los siguientes tres casos:
- Si F(mid) ≥ K && F(mid) < K: Esto significa que el mid actual es la respuesta requerida.
- Si F(mid) < K: Esto significa que el valor actual de mid es menor que el valor requerido de x. Entonces, muévase hacia la derecha, es decir, en la segunda mitad, ya que F(x) es una función creciente.
- Si F(mid) > K: Esto significa que el valor actual de mid es mayor que el valor requerido de x. Entonces, muévase hacia la izquierda, es decir, la primera mitad como F(x) es una función creciente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate value of
// quadratic equation for some x
int func(int A, int B, int C, int x)
{
return (A * x * x + B * x + C);
}
// Function to calculate the minimum
// value of x such that F(x) >= K using
// binary search
int findMinx(int A, int B, int C, int K)
{
// Start and end value for
// binary search
int start = 1;
int end = ceil(sqrt(K));
// Binary Search
while (start <= end) {
int mid = start + (end - start) / 2;
// Computing F(mid) and F(mid-1)
int x = func(A, B, C, mid);
int Y = func(A, B, C, mid - 1);
// Checking the three cases
// If F(mid) >= K and
// F(mid-1) < K return mid
if (x >= K && Y < K) {
return mid;
}
// If F(mid) < K go to mid+1 to end
else if (x < K) {
start = mid + 1;
}
// If F(mid) > K go to start to mid-1
else {
end = mid - 1;
}
}
// If no such value exist
return -1;
}
// Driver Code
int main()
{
// Given coefficients of Equations
int A = 3, B = 4, C = 5, K = 6;
// Find minimum value of x
cout << findMinx(A, B, C, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to calculate value of
// quadratic equation for some x
static int func(int A, int B, int C, int x)
{
return (A * x * x + B * x + C);
}
// Function to calculate the minimum
// value of x such that F(x) >= K using
// binary search
static int findMinx(int A, int B, int C, int K)
{
// Start and end value for
// binary search
int start = 1;
int end = (int)Math.ceil(Math.sqrt(K));
// Binary Search
while (start <= end)
{
int mid = start + (end - start) / 2;
// Computing F(mid) and F(mid-1)
int x = func(A, B, C, mid);
int Y = func(A, B, C, mid - 1);
// Checking the three cases
// If F(mid) >= K and
// F(mid-1) < K return mid
if (x >= K && Y < K)
{
return mid;
}
// If F(mid) < K go to mid+1 to end
else if (x < K)
{
start = mid + 1;
}
// If F(mid) > K go to start to mid-1
else
{
end = mid - 1;
}
}
// If no such value exist
return -1;
}
// Driver code
public static void main(String[] args)
{
// Given coefficients of Equations
int A = 3, B = 4, C = 5, K = 6;
// Find minimum value of x
System.out.println(findMinx(A, B, C, K));
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach import math # Function to calculate value of # quadratic equation for some x def func(A, B, C, x): return (A * x * x + B * x + C) # Function to calculate the minimum # value of x such that F(x) >= K using # binary search def findMinx(A, B, C, K): # Start and end value for # binary search start = 1 end = math.ceil(math.sqrt(K)) # Binary Search while (start <= end): mid = start + (end - start) // 2 # Computing F(mid) and F(mid-1) x = func(A, B, C, mid) Y = func(A, B, C, mid - 1) # Checking the three cases # If F(mid) >= K and # F(mid-1) < K return mid if (x >= K and Y < K): return mid # If F(mid) < K go to mid+1 to end elif (x < K): start = mid + 1 # If F(mid) > K go to start to mid-1 else: end = mid - 1 # If no such value exist return -1 # Driver Code # Given coefficients of Equations A = 3 B = 4 C = 5 K = 6 # Find minimum value of x print(findMinx(A, B, C, K)) # This code is contributed by code_hunt
C#
// C# program for the above approach
using System;
class GFG{
// Function to calculate value of
// quadratic equation for some x
static int func(int A, int B, int C, int x)
{
return (A * x * x + B * x + C);
}
// Function to calculate the minimum
// value of x such that F(x) >= K using
// binary search
static int findMinx(int A, int B, int C, int K)
{
// Start and end value for
// binary search
int start = 1;
int end = (int)Math.Ceiling(Math.Sqrt(K));
// Binary Search
while (start <= end)
{
int mid = start + (end - start) / 2;
// Computing F(mid) and F(mid-1)
int x = func(A, B, C, mid);
int Y = func(A, B, C, mid - 1);
// Checking the three cases
// If F(mid) >= K and
// F(mid-1) < K return mid
if (x >= K && Y < K)
{
return mid;
}
// If F(mid) < K go to mid+1 to end
else if (x < K)
{
start = mid + 1;
}
// If F(mid) > K go to start to mid-1
else
{
end = mid - 1;
}
}
// If no such value exist
return -1;
}
// Driver code
public static void Main(String[] args)
{
// Given coefficients of Equations
int A = 3, B = 4, C = 5, K = 6;
// Find minimum value of x
Console.WriteLine(findMinx(A, B, C, K));
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// javascript program for the above approach
// Function to calculate value of
// quadratic equation for some x
function func(A , B , C , x)
{
return (A * x * x + B * x + C);
}
// Function to calculate the minimum
// value of x such that F(x) >= K using
// binary search
function findMinx(A , B , C , K)
{
// Start and end value for
// binary search
var start = 1;
var end = parseInt(Math.ceil(Math.sqrt(K)));
// Binary Search
while (start <= end)
{
var mid = start + parseInt((end - start) / 2);
// Computing F(mid) and F(mid-1)
var x = func(A, B, C, mid);
var Y = func(A, B, C, mid - 1);
// Checking the three cases
// If F(mid) >= K and
// F(mid-1) < K return mid
if (x >= K && Y < K)
{
return mid;
}
// If F(mid) < K go to mid+1 to end
else if (x < K)
{
start = mid + 1;
}
// If F(mid) > K go to start to mid-1
else
{
end = mid - 1;
}
}
// If no such value exist
return -1;
}
// Driver code
// Given coefficients of Equations
var A = 3, B = 4, C = 5, K = 6;
// Find minimum value of x
document.write(findMinx(A, B, C, K));
// This code is contributed by shikhasingrajput
</script>
Producción:
1
Complejidad de tiempo: O(log(sqrt(K))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por mridulkumar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA