Count of pairs whose sum of pairwise product with X and Y is K
Given an array arr[] of size N and three integers X, Y and K, the task is to count the number of pairs (i, j) where i < j such that (arr[i] * X + arr[j] * Y) = K.
Examples:
Input: arr[] = {3, 1, 2, 3}, X = 4, Y = 2, K = 14
Output: 2
Explanation: The possible pairs are: (1, 2), (3, 4).
For i = 1, j = 2, Value of the expression = 4 * 3 + 2 * 1 = 14.
For i = 3, j = 4, Value of the expression = 4 * 2 + 2 * 3 = 14.Input: arr[] = [1, 3, 2], X = 1, Y = 3, K = 7
Output: 1
Explanation: The possible pairs are: (1, 2).
For i = 1, j = 2, Value of the expression = 1 * 1 + 2 * 3 = 7.Input: N = 2, arr[] = [1, 2], X =1, Y = 1, target = 2
Output: 0
Explanation: No pair satisfy the above condition.
For i = 1, j = 2, Value of the expression = 1 * 1 + 1 * 2 = 3.
Naive Approach: The basic idea to solve the problem is as follows:
Find all possible pairs of (i, j) and for each pair check if (arr[i]*X + arr[j]*Y = K). If so then increment the count of pairs.
Follow the below steps to implement the idea:
- Initialize, an integer variable (say cnt as 0) to store the count of the pairs.
- Loop through the array from i = 0 to N – 2 :
- Loop for all the second elements from j = i + 1 to N-1:
- Check if the sum of arr[i] * X and arr[j] * Y is equal to K.
- Then increment the value of cnt by 1.
- Loop for all the second elements from j = i + 1 to N-1:
- Return the value of cnt as the final answer.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to count the number of pairs int countPairs( int arr[], int n, int x, int y, int k) { // Store the count of the pairs. int cnt = 0; // Loop for the first element. for ( int i = 0; i < n - 1; ++i) { // Loop for the second element. for ( int j = i + 1; j < n; ++j) { // Calculate the sum int cur_sum = arr[i] * x + arr[j] * y; // Increment 'cnt' if current // sum is equal to required target if (cur_sum == k) { cnt++; } } } // Return the count of pairs. return cnt; } // Driver Code int main() { int X = 4, Y = 2, K = 14; int arr[] = { 3, 1, 2, 3 }; int N = sizeof (arr) / sizeof (arr[0]); // Function call cout << countPairs(arr, N, X, Y, K); return 0; } |
Java
// Java program for the above approach import java.util.*; public class GFG { // Function to count the number of pairs static int countPairs( int [] arr, int n, int x, int y, int k) { // Store the count of the pairs. int cnt = 0 ; // Loop for the first element. for ( int i = 0 ; i < n - 1 ; ++i) { // Loop for the second element. for ( int j = i + 1 ; j < n; ++j) { // Calculate the sum int cur_sum = arr[i] * x + arr[j] * y; // Increment 'cnt' if current // sum is equal to required target if (cur_sum == k) { cnt++; } } } // Return the count of pairs. return cnt; } // Driver Code public static void main(String[] args) { int X = 4 , Y = 2 , K = 14 ; int [] arr = { 3 , 1 , 2 , 3 }; int N = arr.length; // Function call System.out.println( countPairs(arr, N, X, Y, K)); } } // This code is contributed by shinjanpatra. |
Python3
# Python code for the above approach # Function to count the number of pairs def countPairs(arr, n, x, y, k) : # Store the count of the pairs. cnt = 0 # Loop for the first element. for i in range (n - 1 ) : # Loop for the second element. for j in range (i + 1 , n) : # Calculate the sum cur_sum = arr[i] * x + arr[j] * y # Increment 'cnt' if current # sum is equal to required target if (cur_sum = = k) : cnt + = 1 # Return the count of pairs. return cnt # Driver Code if __name__ = = "__main__" : X = 4 Y = 2 K = 14 arr = [ 3 , 1 , 2 , 3 ] N = len (arr) # Function call print (countPairs(arr, N, X, Y, K)) # This code is contributed by code_hunt. |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to count the number of pairs static int countPairs( int [] arr, int n, int x, int y, int k) { // Store the count of the pairs. int cnt = 0; // Loop for the first element. for ( int i = 0; i < n - 1; ++i) { // Loop for the second element. for ( int j = i + 1; j < n; ++j) { // Calculate the sum int cur_sum = arr[i] * x + arr[j] * y; // Increment 'cnt' if current // sum is equal to required target if (cur_sum == k) { cnt++; } } } // Return the count of pairs. return cnt; } // Driver Code public static void Main(String[] args) { int X = 4, Y = 2, K = 14; int [] arr = { 3, 1, 2, 3 }; int N = arr.Length; // Function call Console.WriteLine( countPairs(arr, N, X, Y, K)); } } // This code is contributed by avijitmondal1998. |
Javascript
<script> // JavaScript code to implement the approach // Function to count the number of pairs function countPairs(arr, n, x, y, k) { // Store the count of the pairs. var cnt = 0; // Loop for the first element. for ( var i = 0; i < n - 1; ++i) { // Loop for the second element. for ( var j = i + 1; j < n; ++j) { // Calculate the sum var cur_sum = arr[i] * x + arr[j] * y; // Increment 'cnt' if current // sum is equal to required target if (cur_sum == k) { cnt++; } } } // Return the count of pairs. return cnt; } // Driver Code var X = 4; var Y = 2; var K = 14; var arr = [ 3, 1, 2, 3 ]; var N = arr.length; // Function call document.write(countPairs(arr, N, X, Y, K)); // this code is contributed by phasing17. </script> |
2
Time Complexity: O(N2)
Space Complexity: O(1)
Efficient Approach: The problem can be solved efficiently based on the following mathematical observation:
arr[i]*X + arr[j]*Y = K
arr[i]*X = K – arr[j]*Y
So (K – arr[j]*Y) must be divisible by X and if arr[j] is found then the value of arr[i] must be (K – arr[j]*Y)/X.So to solve the problem based on the above observation, consider each value as arr[j] and try to find the presence of arr[i] using the above relation where i is less than j.
The above observation can be implemented using frequency counting. Follow the below steps to solve this problem :
- Initialize a variable (say cnt = 0) to store the count of pairs.
- Create a frequency array freq[] to store the frequency of the array elements.
- Loop through all the elements from j = 0 to N-1:
- Find the value of required arr[i] as shown in the above observation.
- If that element is present then increase the cnt by the frequency of that element.
- Increase the frequency of arr[j].
- Return the value of cnt as the final answer.
Below is the implementation of the above approach :
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find the count of pairs int countPairs( int arr[], int n, int x, int y, int k) { // Variable to store count of the pairs int cnt = 0; // Map for storing the frequency unordered_map< int , int > freq; // Loop for finding the count of pairs for ( int i = 0; i < n; ++i) { // RHS Value of the equation given // in approach. int rhs = k - arr[i] * y; // If RHS value is not divisible by // x or is negative, there is no pair // possible for 'arr[i]' as second // element. if (rhs % x || rhs <= 0) { // Update the frequency of arr[i] freq[arr[i]]++; continue ; } rhs /= x; // Adding frequency of rhs in array cnt += freq[rhs]; // Update the frequency of arr[i] freq[arr[i]]++; } // Return the count of pairs return cnt; } // Driver Code int main() { int X = 4, Y = 2, K = 14; int arr[] = { 3, 1, 2, 3 }; int N = sizeof (arr) / sizeof (arr[0]); // Function call cout << countPairs(arr, N, X, Y, K); return 0; } |
Java
// Java program to implement // the above approach import java.util.*; public class GFG { // Function to find the count of pairs static int countPairs( int [] arr, int n, int x, int y, int k) { // Variable to store count of the pairs int cnt = 0 ; // Map for storing the frequency Map<Integer,Integer> freq = new HashMap<Integer,Integer>(); for ( int i = 0 ; i < n; i++) { if (freq.containsKey(arr[i])){ freq.put(arr[i], freq.get(arr[i]) + 0 ); } else { freq.put(arr[i], 0 ); } } // Loop for finding the count of pairs for ( int i = 0 ; i < n; ++i) { // RHS Value of the equation given // in approach. int rhs = k - arr[i] * y; // If RHS value is not divisible by // x or is negative, there is no pair // possible for 'arr[i]' as second // element. if ((rhs % x) != 0 || rhs <= 0 ) { // Update the frequency of arr[i] freq.put(arr[i], freq.get(arr[i])+ 1 ); continue ; } rhs /= x; // Adding frequency of rhs in array cnt += freq.get(rhs); // Update the frequency of arr[i] freq.put(arr[i], freq.get(arr[i])+ 1 ); } // Return the count of pairs return cnt; } // Driver Code public static void main(String []args) { int X = 4 , Y = 2 , K = 14 ; int [] arr = { 3 , 1 , 2 , 3 }; int N = arr.length; // Function call System.out.print(countPairs(arr, N, X, Y, K)); } } // This code is contributed by AnkThon |
Python3
# Python3 program for the above approach # Function to find the count of pairs def countPairs(arr, n, x, y, k): # Variable to store count of the pairs cnt = 0 # Dictionary for storing the frequency freq = dict () # Loop for finding the count of pairs for i in range (n): # RHS Value of the equation given # in approach. rhs = k - arr[i] * y; # If RHS value is not divisible by # x or is negative, there is no pair # possible for 'arr[i]' as second # element. if (rhs % x or rhs < = 0 ) : # Update the frequency of arr[i] if arr[i] in freq: freq[arr[i]] + = 1 else : freq[arr[i]] = 1 continue rhs = rhs / / x # Adding frequency of rhs in array if rhs in freq: cnt + = freq[rhs] # Update the frequency of arr[i] if arr[i] in freq: freq[arr[i]] + = 1 else : freq[arr[i]] = 1 # Return the count of pairs return cnt; # Driver Code X = 4 Y = 2 K = 14 ; arr = [ 3 , 1 , 2 , 3 ] N = len (arr) # Function Call print (countPairs(arr, N, X, Y, K)) # This code is contributed by phasing17 |
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG { // Function to find the count of pairs static int countPairs( int [] arr, int n, int x, int y, int k) { // Variable to store count of the pairs int cnt = 0; // Map for storing the frequency Dictionary< int , int > freq = new Dictionary< int , int >(); for ( int i = 0; i < n; i++) { if (freq.ContainsKey(arr[i])){ freq[arr[i]] = freq[arr[i]] + 0; } else { freq.Add(arr[i], 0); } } // Loop for finding the count of pairs for ( int i = 0; i < n; ++i) { // RHS Value of the equation given // in approach. int rhs = k - arr[i] * y; // If RHS value is not divisible by // x or is negative, there is no pair // possible for 'arr[i]' as second // element. if ((rhs % x) != 0 || rhs <= 0) { // Update the frequency of arr[i] // Update the frequency of arr[i] freq[arr[i]]++; continue ; } rhs /= x; // Adding frequency of rhs in array cnt += freq[rhs]; // Update the frequency of arr[i] freq[arr[i]]++; } // Return the count of pairs return cnt; } // Driver Code public static void Main() { int X = 4, Y = 2, K = 14; int [] arr = { 3, 1, 2, 3 }; int N = arr.Length; // Function call Console.Write(countPairs(arr, N, X, Y, K)); } } |
Javascript
<script> // JavaScript program for the above approach // Function to find the count of pairs function countPairs(arr, n, x, y, k) { // Variable to store count of the pairs let cnt = 0; // Map for storing the frequency let freq = new Map(); // Loop for finding the count of pairs for (let i = 0; i < n; ++i) { // RHS Value of the equation given // in approach. let rhs = k - arr[i] * y; // If RHS value is not divisible by // x or is negative, there is no pair // possible for 'arr[i]' as second // element. if (rhs % x || rhs <= 0) { // Update the frequency of arr[i] if (freq.has(arr[i])) { freq.set(arr[i], freq.get(arr[i]) + 1) } else { freq.set(arr[i], 1) } continue ; } rhs = Math.floor(rhs / x); // Adding frequency of rhs in array if (freq.has(arr[i])) cnt += freq.get(arr[i]) + 1; // Update the frequency of arr[i] if (freq.has(arr[i])) freq.set(arr[i], freq.get(arr[i]) + 1) else freq.set(arr[i], 1) } // Return the count of pairs return cnt; } // Driver Code let X = 4, Y = 2, K = 14; let arr = [3, 1, 2, 3]; let N = arr.length; // Function call document.write(countPairs(arr, N, X, Y, K)); // This code is contributed by Potta Lokesh </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us