Count of pairs of elements with Sum X and multiplication Y in given Array
Given array A[] (-109 <= A[i] <= 109) of size N (2 <= N <= 107) along with integers X (-2*109 <= X <= 2*109) and Y (-1018 <= Y <= 1018), the task for this problem is to find the count of pairs (A[i], A[j]) such that X = A[i] + A[j] and Y = A[i] * A[j] also i < j. Also A[i], X, Y != 0
Examples:
Input: A[] = {1, 4, -2, 3, 3, 3}, X = 7, Y = 12
Output: 3
Explanation: pairs (A[2], A[4]) = (4, 3), (A[2], A[5]) = (4, 3), and (A[2], A[6]) = (4, 3) are the pairs which satisfy above conditions.Input: A[] = {1, 3, 2}, X = 5, Y = 6
Output: 1
Explanation: There is only one pair (A[2], A[3]) = (3, 2) which satisfy above conditions (X = A[2] + A[3] = 5 and Y = A[2] * A[3] = 6).
Naïve Approach: The basic way to solve the problem is as follows:
Simply iterating with two loops and maintaining a counter of pairs which satisfy above conditions.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: To solve the problem follow the below idea:
If X = A[i] + A[j] and Y = A[i] * A[j] then a2 – Xa + Y = 0 which is Quadratic equation in terms of sum and product of roots.
Here roots are A[i] and A[j]. so we just have to find the count of roots of quadratic equation in array A[] their multiplication will be answer. If the roots are integers then only its possible to find them in array otherwise answer will be zero. Here root will be (X + sqrt(Discriminant)) / 2 and (X – sqrt(Discriminant)) / 2 where Discriminant = X * X – 4 * Y.
Below are the steps for the above approach:
- Creating Variable for discriminant and calculate it.
- Check condition whether roots are integers or not. if not integer return 0.
- Find both the roots by above formula.
- If Discriminant is zero then there will be only one unique root find its count as cntRoot in array A[] and return answer: cntRoot * (cntRoot – 1) / 2.
- If Discriminant is not zero then find count of both the roots as firstRootCnt and secondRootCnt then return answer as : firstRootCnt * secondRootCnt.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function will tell whether given // number is perfect square or not bool isPerfectSquare( int number) { return sqrt (number) * sqrt (number) == number; } // Function to find count of pairs of integers // with Sum X and multiplication Y int findPairCount( int A[], int N, int X, int Y) { // Creating Variable for discriminant int discriminant = X * X - 4 * Y; // Check if both the roots are // integers or not if (isPerfectSquare(discriminant) and (X + ( int ) sqrt (discriminant)) % 2 == 0 and (X - ( int ) sqrt (discriminant)) % 2 == 0) { // First and second root int firstRoot = (X + sqrt (discriminant)) / 2; int secondRoot = (X - sqrt (discriminant)) / 2; // If both roots are same that is // discriminant is zero if (discriminant == 0) { // Variable that track count // of cntRoot int cntRoot = 0; // Find count of given root for ( int i = 0; i < N; i++) { if (A[i] == firstRoot) cntRoot++; } // Answer in this case will be number // of ways of choosing 2 elements // from cntRoot return cntRoot * (cntRoot - 1) / 2; } else { // Find count of given roots int firstRootCnt = 0, secondRootCnt = 0; // Find count of given roots for ( int i = 0; i < N; i++) { if (firstRoot == A[i]) firstRootCnt++; else if (secondRoot == A[i]) secondRootCnt++; } // answer will be number of ways of // choosing one element rom // firstRootCnt and one element // from second RootCnt; return firstRootCnt * secondRootCnt; } } // If roots are not interger then return 0 else { return 0; } } // Driver Code int32_t main() { // Input 1 int X = 7, Y = 12; int A[] = { 1, 4, -2, 3, 3, 3 }, N = 6; // Function Call cout << findPairCount(A, N, X, Y) << endl; // Input 2 int X1 = 5, Y1 = 6; int A1[] = { 1, 3, 2 }, N1 = 3; // Function Call cout << findPairCount(A1, N1, X1, Y1) << endl; return 0; } |
Java
import java.util.Arrays; public class Solution { // Function will tell whether given number is a perfect square or not static boolean isPerfectSquare( int number) { int sqrt = ( int ) Math.sqrt(number); return sqrt * sqrt == number; } // Function to find the count of pairs of integers with Sum X and multiplication Y static int findPairCount( int [] A, int N, int X, int Y) { // Creating Variable for discriminant int discriminant = X * X - 4 * Y; // Check if both the roots are integers or not if (isPerfectSquare(discriminant) && (X + ( int ) Math.sqrt(discriminant)) % 2 == 0 && (X - ( int ) Math.sqrt(discriminant)) % 2 == 0 ) { // First and second root int firstRoot = (X + ( int ) Math.sqrt(discriminant)) / 2 ; int secondRoot = (X - ( int ) Math.sqrt(discriminant)) / 2 ; // If both roots are the same, that is discriminant is zero if (discriminant == 0 ) { // Variable that tracks the count of cntRoot int cntRoot = 0 ; // Find count of given root for ( int i = 0 ; i < N; i++) { if (A[i] == firstRoot) cntRoot++; } // Answer in this case will be the number of ways of choosing 2 elements from cntRoot return cntRoot * (cntRoot - 1 ) / 2 ; } else { // Find count of given roots int firstRootCnt = 0 , secondRootCnt = 0 ; // Find count of given roots for ( int i = 0 ; i < N; i++) { if (firstRoot == A[i]) firstRootCnt++; else if (secondRoot == A[i]) secondRootCnt++; } // Answer will be the number of ways of choosing one element from firstRootCnt and one element from secondRootCnt; return firstRootCnt * secondRootCnt; } } // If roots are not integers, then return 0 else { return 0 ; } } // Driver Code public static void main(String[] args) { // Input 1 int X = 7 , Y = 12 ; int [] A = { 1 , 4 , - 2 , 3 , 3 , 3 }; int N = 6 ; // Function Call System.out.println(findPairCount(A, N, X, Y)); // Input 2 int X1 = 5 , Y1 = 6 ; int [] A1 = { 1 , 3 , 2 }; int N1 = 3 ; // Function Call System.out.println(findPairCount(A1, N1, X1, Y1)); } } |
Python3
# Function to check if a number is a perfect square def isPerfectSquare(number): root = int (number * * 0.5 ) return root * root = = number # Function to find the count of pairs of integers # with Sum X and multiplication Y def findPairCount(A, N, X, Y): # Creating a variable for the discriminant discriminant = X * X - 4 * Y # Check if both the roots are integers or not if isPerfectSquare(discriminant): root = int (discriminant * * 0.5 ) if (X + root) % 2 = = 0 and (X - root) % 2 = = 0 : # First and second root firstRoot = (X + root) / / 2 secondRoot = (X - root) / / 2 # If both roots are the same (discriminant is zero) if discriminant = = 0 : # Variable that tracks the count of cntRoot cntRoot = 0 # Find the count of the given root for i in range (N): if A[i] = = firstRoot: cntRoot + = 1 # Answer in this case will be the number # of ways of choosing 2 elements from cntRoot return cntRoot * (cntRoot - 1 ) / / 2 else : # Find the count of given roots firstRootCnt = 0 secondRootCnt = 0 # Find count of given roots for i in range (N): if firstRoot = = A[i]: firstRootCnt + = 1 elif secondRoot = = A[i]: secondRootCnt + = 1 # Answer will be the number of ways of # choosing one element from # firstRootCnt and one element # from secondRootCnt; return firstRootCnt * secondRootCnt # If roots are not integers, then return 0 return 0 # Driver Code def main(): # Input 1 X = 7 Y = 12 A = [ 1 , 4 , - 2 , 3 , 3 , 3 ] N = 6 # Function Call print (findPairCount(A, N, X, Y)) # Input 2 X1 = 5 Y1 = 6 A1 = [ 1 , 3 , 2 ] N1 = 3 # Function Call print (findPairCount(A1, N1, X1, Y1)) if __name__ = = "__main__" : main() |
C#
using System; public class GFG { // Function will tell whether given number is a perfect square or not static bool IsPerfectSquare( int number) { int sqrt = ( int )Math.Sqrt(number); return sqrt * sqrt == number; } // Function to find the count of pairs of integers with Sum X and multiplication Y static int FindPairCount( int [] A, int N, int X, int Y) { // Creating Variable for discriminant int discriminant = X * X - 4 * Y; // Check if both the roots are integers or not if (IsPerfectSquare(discriminant) && (X + ( int )Math.Sqrt(discriminant)) % 2 == 0 && (X - ( int )Math.Sqrt(discriminant)) % 2 == 0) { // First and second root int firstRoot = (X + ( int )Math.Sqrt(discriminant)) / 2; int secondRoot = (X - ( int )Math.Sqrt(discriminant)) / 2; // If both roots are the same, that is discriminant is zero if (discriminant == 0) { // Variable that tracks the count of cntRoot int cntRoot = 0; // Find count of given root for ( int i = 0; i < N; i++) { if (A[i] == firstRoot) cntRoot++; } // Answer in this case will be the number of ways of choosing 2 elements from cntRoot return cntRoot * (cntRoot - 1) / 2; } else { // Find count of given roots int firstRootCnt = 0, secondRootCnt = 0; // Find count of given roots for ( int i = 0; i < N; i++) { if (firstRoot == A[i]) firstRootCnt++; else if (secondRoot == A[i]) secondRootCnt++; } // Answer will be the number of ways of choosing one element from firstRootCnt and one element from secondRootCnt; return firstRootCnt * secondRootCnt; } } // If roots are not integers, then return 0 else { return 0; } } // Driver Code public static void Main( string [] args) { // Input 1 int X = 7, Y = 12; int [] A = { 1, 4, -2, 3, 3, 3 }; int N = 6; // Function Call Console.WriteLine(FindPairCount(A, N, X, Y)); // Input 2 int X1 = 5, Y1 = 6; int [] A1 = { 1, 3, 2 }; int N1 = 3; // Function Call Console.WriteLine(FindPairCount(A1, N1, X1, Y1)); } } |
Javascript
function GFG(number) { const sqrt = Math.sqrt(number); return Math.floor(sqrt) * Math.floor(sqrt) === number; } // Function to find the count of pairs of integers with // Sum X and multiplication Y function Count(A, N, X, Y) { // Creating a variable for the discriminant const discriminant = X * X - 4 * Y; // Check if both the roots are integers or not if (GFG(discriminant) && (X + Math.sqrt(discriminant)) % 2 === 0 && (X - Math.sqrt(discriminant)) % 2 === 0) { // First and second root const firstRoot = (X + Math.sqrt(discriminant)) / 2; const secondRoot = (X - Math.sqrt(discriminant)) / 2; // If both roots are the same // that is discriminant is zero if (discriminant === 0) { // Variable that tracks the count of cntRoot let cntRoot = 0; // Find count of given root for (let i = 0; i < N; i++) { if (A[i] === firstRoot) cntRoot++; } // Answer in this case will be the number of ways of // choosing 2 elements from cntRoot return (cntRoot * (cntRoot - 1)) / 2; } else { // Find count of given roots let firstRootCnt = 0; let secondRootCnt = 0; // Find count of given roots for (let i = 0; i < N; i++) { if (firstRoot === A[i]) firstRootCnt++; else if (secondRoot === A[i]) secondRootCnt++; } // Answer will be the number of ways of choosing one element from // firstRootCnt and one element from secondRootCnt; return firstRootCnt * secondRootCnt; } } // If roots are not integers, then return 0 else { return 0; } } // Driver Code // Input 1 const X = 7; const Y = 12; const A = [1, 4, -2, 3, 3, 3]; const N = 6; // Function Call console.log(Count(A, N, X, Y)); // Input 2 const X1 = 5; const Y1 = 6; const A1 = [1, 3, 2]; const N1 = 3; // Function Call console.log(Count(A1, N1, X1, Y1)); |
3 1
Time Complexity: O(N)
Auxiliary Space: O(1)
Related Articles:
- Array Data Structure
- Quadratic Equations