Cuente tripletes de una array que puede formar ecuaciones cuadráticas con raíces reales

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:
    1. 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.
    2. 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.
    3. 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 .
    1. Inicialice dos variables a y c con 0 y tamaño de array igual a -1 , respectivamente.
    2. Ejecute un bucle mientras a < c se cumpla y verifique las siguientes condiciones:
      1. Si a = b , entonces incremente a y continúe el ciclo.
      2. Si c = b , entonces disminuya c y continúe el ciclo.
      3. 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.
      4. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *