Given an array arr[] consisting of N distinct positive integers, the task is to find the count of triplets (a, b, c) such that the quadratic equation aX2 + bX + c = 0 has real roots.
Examples:
Input: arr[] = { 2, 3, 6, 8 }
Output: 6
Explanation:
For the triplets (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)}, the quadratic equation 2X2 + 6X + 3 = 0 has real roots.Input: arr[] = [1, 2, 3, 4, 5]
Output: 14
Naive Approach: A quadratic equation has real roots if its determinant is less than or equal to 0. Therefore, a * c ? b * b / 4. The problem can be solved by using this property.
Follow the steps given below to solve the problem:
- Iterate over the range [0, N – 1] using a variable, say b, and perform the following steps:
- For each value of b, run a loop from a = 0 to N – 1 and check if b and a are equal or not. If found to be true, then continue the loop.
- Now, iterate over the range [0, N – 1] using a variable, say c, and check if both b = c or a = c are satisfied or not. If found to be true, then continue the loop.
- If arr[a] * arr[C] ? arr[b] * arr[b] / 4, then increment the count.
- Finally, return the count.
Below is the implementation of the above approach:
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 rootsint 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 Codeint 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 approachimport java.util.*;class GFG{// Function to find count of triplets (a, b, c)// such that the equations ax^2 + bx + c = 0 // has real rootsstatic 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 Codepublic 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 rootsdef 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 codearr = [1,2,3,4,5]N = len(arr)print(getcount(arr, N))# This code is contributed by Virusbuddah |
C#
// C# program for the above approachusing 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 rootsfunction 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 Codevar arr = [ 1, 2, 3, 4, 5 ];var N = arr.length;// Function Calldocument.write(getCount(arr, N));// This code is contributed by Ankita saini</script> |
Output:
14
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient approach: The problem can be solved efficiently by Using sorting and two pointers algorithm.
Follow the below steps to solve the problem:
- Sort the given array arr[] in ascending order.
- Run a loop from b = 0 to the size of the array.
- Initialize two variables a and c with 0 and size of array equal to -1, respectively.
- Run a loop while a < c holds true and check for the following conditions:
- If a = b, then increment a and continue the loop.
- If c = b, then decrement c and continue the loop.
- If arr[a] * arr[C] ? d, then check for the following conditions:
- If a < b < c , then increase count by number of elements between them – 1(except arr[b]).
- Otherwise, increase count by the number of elements between them.
- Otherwise, decrement c.
- For each pair, two values are possible of a and c. So return count * 2.
Below is the implementation of the above approach:
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 rootsint 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 Codeint 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 approachimport 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 rootsstatic 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 Codepublic 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 rootsdef 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 codearr = [3,6,10,13,21]N = len(arr)print(getcount(arr,N))# This code is contributed by Virusbuddah |
C#
// C# program for the above approachusing 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 rootsfunction 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 Codevar arr = [ 3, 6, 10, 13, 21 ];var N = arr.length;// Function Calldocument.write(getCount(arr, N)); // This code is contributed by Ankita saini</script> |
Output:
16
Time Complexity: O(N2)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
