Dada una array arr[] que consiste en N enteros positivos distintos, la tarea es encontrar el conteo de tripletes (a, b, c) tal que la ecuación cuadrática aX 2 + bX + c = 0 tenga raíces reales .
Ejemplos:
Entrada: arr[] = { 2, 3, 6, 8 }
Salida: 6
Explicación:
Para los tripletes (a = 2, b = 6, c = 3), (a = 3, b = 6, c = 2) , (a = 2, b = 8, c = 3), (a = 3, b = 8, c = 2), (a = 2, b = 8, c = 6), (a = 6, b = 8, c = 2)}, la ecuación cuadrática 2X 2 + 6X + 3 = 0 tiene raíces reales.Entrada: arr[] = [1, 2, 3, 4, 5]
Salida: 14
Enfoque ingenuo: una ecuación cuadrática tiene raíces reales si su determinante es menor o igual a 0 . Por lo tanto, a * c ≤ b * b / 4 . El problema se puede resolver usando esta propiedad.
Siga los pasos que se indican a continuación para resolver el problema:
- Itere sobre el rango [0, N – 1] usando una variable, digamos b , y realice los siguientes pasos:
- Para cada valor de b , ejecute un bucle desde a = 0 hasta N – 1 y verifique si b y a son iguales o no. Si se encuentra que es cierto, entonces continúe el ciclo.
- Ahora, itere sobre el rango [0, N – 1] usando una variable, digamos c , y verifique si tanto b = c como a = c están satisfechos o no. Si se encuentra que es cierto, entonces continúe el bucle.
- Si arr[a] * arr[C] ≤ arr[b] * arr[b] / 4 , entonces incremente el conteo.
- Por último, devuelve la cuenta .
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 find count of triplets (a, b, c)
// such that the equations ax^2 + bx + c = 0
// has real roots
int getCount(int arr[], int N)
{
// Stores count of triplets(a, b, c) such
// that ax^2 + bx + c = 0 has real roots
int count = 0;
// Base case
if (N < 3)
return 0;
// Generate all possible triplets(a, b, c)
for (int b = 0; b < N; b++) {
for (int a = 0; a < N; a++) {
// If the coefficient of
// X^2 and X are equal
if (a == b)
continue;
for (int c = 0; c < N; c++) {
// If coefficient of X^2
// or x are equal to the
// constant
if (c == a || c == b)
continue;
int d = arr[b] * arr[b] / 4;
// Condition for having
// real roots
if (arr[a] * arr <= d)
count++;
}
}
}
return count;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 5 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << getCount(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find count of triplets (a, b, c)
// such that the equations ax^2 + bx + c = 0
// has real roots
static int getCount(int arr[], int N)
{
// Stores count of triplets(a, b, c) such
// that ax^2 + bx + c = 0 has real roots
int count = 0;
// Base case
if (N < 3)
return 0;
// Generate all possible triplets(a, b, c)
for (int b = 0; b < N; b++)
{
for (int a = 0; a < N; a++)
{
// If the coefficient of
// X^2 and X are equal
if (a == b)
continue;
for (int c = 0; c < N; c++)
{
// If coefficient of X^2
// or x are equal to the
// constant
if (c == a || c == b)
continue;
int d = arr[b] * arr[b] / 4;
// Condition for having
// real roots
if (arr[a] * arr <= d)
count++;
}
}
}
return count;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 4, 5 };
int N = arr.length;
// Function Call
System.out.print(getCount(arr, N));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python Program for the above approach # Function to find the count of triplets(a,b,c) # Such that the equations ax^2 + bx + c = 0 # has real roots def getcount(arr,N): # store count of triplets(a,b,c) such # that ax^2 + bx + c = 0 has real roots count = 0 # base case if (N < 3): return 0 # Generate all possible triplets (a,b,c) for b in range(0, N): for a in range(0, N): # if the coefficient of X^2 # and x are equal if (a == b): continue for c in range(0, N): # if coefficient of X^2 # or x are equal to the # constant if (c == a or c == b): continue d = arr[b] * arr[b] // 4 # condition for having # real roots if (arr[a] * arr) <= d: count += 1 return count # Driver code arr = [1,2,3,4,5] N = len(arr) print(getcount(arr, N)) # This code is contributed by Virusbuddah
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to find count of triplets (a, b, c)
// such that the equations ax^2 + bx + c = 0
// has real roots
static int getCount(int[] arr, int N)
{
// Stores count of triplets(a, b, c) such
// that ax^2 + bx + c = 0 has real roots
int count = 0;
// Base case
if (N < 3)
return 0;
// Generate all possible triplets(a, b, c)
for (int b = 0; b < N; b++)
{
for (int a = 0; a < N; a++)
{
// If the coefficient of
// X^2 and X are equal
if (a == b)
continue;
for (int c = 0; c < N; c++)
{
// If coefficient of X^2
// or x are equal to the
// constant
if (c == a || c == b)
continue;
int d = arr[b] * arr[b] / 4;
// Condition for having
// real roots
if (arr[a] * arr <= d)
count++;
}
}
}
return count;
}
// Driver Code
static public void Main()
{
int[] arr = { 1, 2, 3, 4, 5 };
int N = arr.Length;
// Function Call
Console.WriteLine(getCount(arr, N));
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// Javascript program for the above approach
// Function to find count of triplets (a, b, c)
// such that the equations ax^2 + bx + c = 0
// has real roots
function getCount(arr, N)
{
// Stores count of triplets(a, b, c) such
// that ax^2 + bx + c = 0 has real roots
var count = 0;
// Base case
if (N < 3)
return 0;
// Generate all possible triplets(a, b, c)
for(var b = 0; b < N; b++)
{
for(var a = 0; a < N; a++)
{
// If the coefficient of
// X^2 and X are equal
if (a == b)
continue;
for(var c = 0; c < N; c++)
{
// If coefficient of X^2
// or x are equal to the
// constant
if (c == a || c == b)
continue;
var d = arr[b] * arr[b] / 4;
// Condition for having
// real roots
if (arr[a] * arr <= d)
count++;
}
}
}
return count;
}
// Driver Code
var arr = [ 1, 2, 3, 4, 5 ];
var N = arr.length;
// Function Call
document.write(getCount(arr, N));
// This code is contributed by Ankita saini
</script>
Producción:
14
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente : el problema se puede resolver de manera eficiente utilizando la clasificación y el algoritmo de dos punteros .
Siga los pasos a continuación para resolver el problema:
- Ordene la array dada arr[] en orden ascendente .
- Ejecute un ciclo desde b = 0 hasta el tamaño de la array .
- Inicialice dos variables a y c con 0 y tamaño de array igual a -1 , respectivamente.
- Ejecute un bucle mientras a < c se cumpla y verifique las siguientes condiciones:
- Si a = b , entonces incremente a y continúe el ciclo.
- Si c = b , entonces disminuya c y continúe el ciclo.
- Si arr[a] * arr[C] ≤ d , compruebe las siguientes condiciones:
- Si a < b < c , aumente el número de elementos entre ellos – 1 ( excepto arr[b] ).
- De lo contrario, aumente la cuenta por el número de elementos entre ellos.
- De lo contrario, disminuya c .
- Para cada par, son posibles dos valores de a y c . Así que devuelve count * 2 .
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 count the number of triplets
// (a, b, c) such that the equation
// ax^2 + bx + c = 0 has real roots
int getCount(int arr[], int N)
{
// Sort the array in
// ascending order
sort(arr, arr + N);
// Stores count of triplets(a, b, c) such
// that ax^2 + bx + c = 0 has real roots
int count = 0;
// Base case
if (N < 3)
return 0;
// Traverse the given array
for (int b = 0; b < N; b++) {
int a = 0, c = N - 1;
int d = arr[b] * arr[b] / 4;
while (a < c) {
// If values of a and
// c are equal to b
if (a == b) {
// Increment a
a++;
continue;
}
if (c == b) {
// Decrement c
c--;
continue;
}
// Condition for having real
// roots for a quadratic equation
if (arr[a] * arr <= d) {
// If b lies in
// between a and c
if (a < b && b < c) {
// Update count
count += c - a - 1;
}
else {
// Update count
count += c - a;
}
// Increment a
a++;
}
else {
// Decrement c
c--;
}
}
}
// For each pair two values
// are possible of a and c
return count * 2;
}
// Driver Code
int main()
{
int arr[] = { 3, 6, 10, 13, 21 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << getCount(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to count the number of triplets
// (a, b, c) such that the equation
// ax^2 + bx + c = 0 has real roots
static int getCount(int arr[], int N)
{
// Sort the array in
// ascending order
Arrays.sort(arr);
// Stores count of triplets(a, b, c) such
// that ax^2 + bx + c = 0 has real roots
int count = 0;
// Base case
if (N < 3)
return 0;
// Traverse the given array
for (int b = 0; b < N; b++)
{
int a = 0, c = N - 1;
int d = arr[b] * arr[b] / 4;
while (a < c)
{
// If values of a and
// c are equal to b
if (a == b)
{
// Increment a
a++;
continue;
}
if (c == b)
{
// Decrement c
c--;
continue;
}
// Condition for having real
// roots for a quadratic equation
if (arr[a] * arr <= d)
{
// If b lies in
// between a and c
if (a < b && b < c)
{
// Update count
count += c - a - 1;
}
else
{
// Update count
count += c - a;
}
// Increment a
a++;
}
else {
// Decrement c
c--;
}
}
}
// For each pair two values
// are possible of a and c
return count * 2;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 3, 6, 10, 13, 21 };
int N = arr.length;
// Function Call
System.out.print(getCount(arr, N));
}
}
// This code is contributed by code_hunt.
Python3
# Python3 Program for the above approach # Function to count the number of triplets(a,b,c) # Such that the equations ax^2 + bx + c = 0 # has real roots def getcount(arr, N): # sort he array in # ascending order arr.sort() # store count of triplets (a,b,c) such # that ax^2 + bx + c = 0 has real roots count = 0 # base case if (N < 3): return 0 # Traverse the given array for b in range(0, N): a = 0 c = N - 1 d = arr[b] * arr[b] // 4 while(a < c): # if value of a and # c are equal to b if (a == b): # increment a a += 1 continue if (c == b): # Decrement c c -= 1 continue # condition for having real # roots for a quadratic equation if (arr[a] * arr) <= d: # if b lies in # between a and c if (a < b and b < c): # update count count += c - a - 1 else: # update count count += c - a # increment a a += 1 else: # Decrement c c -= 1 # for each pair two values # are possible of a and c return count * 2 # Driver code arr = [3,6,10,13,21] N = len(arr) print(getcount(arr,N)) # This code is contributed by Virusbuddah
C#
// C# program for the above approach
using System;
class GFG{
// Function to count the number of triplets
// (a, b, c) such that the equation
// ax^2 + bx + c = 0 has real roots
static int getCount(int[] arr, int N)
{
// Sort the array in
// ascending order
Array.Sort(arr);
// Stores count of triplets(a, b, c) such
// that ax^2 + bx + c = 0 has real roots
int count = 0;
// Base case
if (N < 3)
return 0;
// Traverse the given array
for (int b = 0; b < N; b++)
{
int a = 0, c = N - 1;
int d = arr[b] * arr[b] / 4;
while (a < c)
{
// If values of a and
// c are equal to b
if (a == b)
{
// Increment a
a++;
continue;
}
if (c == b)
{
// Decrement c
c--;
continue;
}
// Condition for having real
// roots for a quadratic equation
if (arr[a] * arr <= d)
{
// If b lies in
// between a and c
if (a < b && b < c)
{
// Update count
count += c - a - 1;
}
else
{
// Update count
count += c - a;
}
// Increment a
a++;
}
else {
// Decrement c
c--;
}
}
}
// For each pair two values
// are possible of a and c
return count * 2;
}
// Driver Code
static public void Main()
{
int[] arr = { 3, 6, 10, 13, 21 };
int N = arr.Length;
// Function Call
Console.Write(getCount(arr, N));
}
}
// This code is contributed by susmitakundugoaldanga.
Javascript
<script>
// Javascript program for the above approach
// Function to count the number of triplets
// (a, b, c) such that the equation
// ax^2 + bx + c = 0 has real roots
function getCount(arr, N)
{
// Sort the array in
// ascending order
arr.sort();
// Stores count of triplets(a, b, c) such
// that ax^2 + bx + c = 0 has real roots
var count = 0;
// Base case
if (N < 3)
return 0;
// Traverse the given array
for(var b = 0; b < N; b++)
{
var a = 0, c = N - 1;
var d = arr[b] * arr[b] / 4;
while (a < c)
{
// If values of a and
// c are equal to b
if (a == b)
{
// Increment a
a++;
continue;
}
if (c == b)
{
// Decrement c
c--;
continue;
}
// Condition for having real
// roots for a quadratic equation
if (arr[a] * arr <= d)
{
// If b lies in
// between a and c
if (a < b && b < c)
{
// Update count
count += c - a - 1;
}
else
{
// Update count
count += c - a;
}
// Increment a
a++;
}
else
{
// Decrement c
c--;
}
}
}
// For each pair two values
// are possible of a and c
return count * 2;
}
// Driver Code
var arr = [ 3, 6, 10, 13, 21 ];
var N = arr.length;
// Function Call
document.write(getCount(arr, N));
// This code is contributed by Ankita saini
</script>
Producción:
16
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por srijanbhardwaj52 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA