Horje
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 &lt;bits/stdc++.h&gt;
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 &lt; 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 &lt; 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 &lt;&lt; findPairCount(A, N, X, Y) &lt;&lt; endl;

    // Input 2
    int X1 = 5, Y1 = 6;
    int A1[] = { 1, 3, 2 }, N1 = 3;

    // Function Call
    cout &lt;&lt; findPairCount(A1, N1, X1, Y1) &lt;&lt; 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));
    }
}
Python 
# 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));

Output
3
1

Time Complexity: O(N)
Auxiliary Space: O(1)

Related Articles:


 


Reffered: https://www.geeksforgeeks.org

Arrays

Related
Set entire Matrix row and column as Zeroes (Set Matrix Zeroes) Set entire Matrix row and column as Zeroes (Set Matrix Zeroes)
Sum of Count of Unique Numbers in all Subarrays Sum of Count of Unique Numbers in all Subarrays
Find K-Avoiding Array Find K-Avoiding Array
Colorful box arrangement with Removal Constraint Colorful box arrangement with Removal Constraint
PreComputation Technique on Arrays PreComputation Technique on Arrays

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 12



 

Horje