Count all pairs of given product
In this article, we will tackle the problem of counting pairs of elements in an array that multiply to a given product. We will explain the problem statement, mentioned a detailed description, and walk through the solution step by step.
Problem Statement
Given an array of integers and a target product, the task is to count all pairs of elements in the array that, when multiplied, result in the given product.
Description
Imagine you have an array of numbers, and you are interested in finding pairs of elements in the array whose product matches a specified value. This problem has practical applications in various domains, such as finance, data analysis, and computer science. For instance, it can be used to find stock prices that, when multiplied, yield a particular investment return.
Example
Let's consider the following array:
int arr[] = {5, 7, 4, 2, -2, -5, 10, 1, 20};
Now, we want to count pairs of elements in this array that multiply to a specific product. Let's take three different product values as examples: 10, 40, and 60.
-
For a product of 10, there are 3 pairs that meet this condition:
- (5, 2)
- (-2, -5)
- (10, 1)
-
For a product of 40, there are 2 pairs:
- (5, 8)
- (2, 20)
-
For a product of 60, there are no pairs in the array that match this condition.
Idea to Solve the Problem
To solve this problem, we can use a nested loop to iterate through the array and compare the product of each pair of elements with the target product. If they match, we increment a counter. The key steps to solve this problem are as follows:
- Iterate through the array using a nested loop to consider each pair of elements.
- For each pair, calculate their product.
- Compare the calculated product with the target product.
- If they match, increment a counter.
Standard Pseudocode
Here is the standard pseudocode for solving this problem:
function count_product(arr, size, product)
counter = 0
for i from 0 to size-1
for j from i+1 to size-1
if arr[i] * arr[j] == product
increment counter by 1
return counter
Algorithm with Explanation
Let's break down the algorithm step by step:
- Initialize a counter to zero, which will keep track of the number of pairs that meet the condition.
- Use a nested loop to iterate through the array. The outer loop (indexed by
i
) will go from the first element to the second-to-last element. - Inside the outer loop, start another loop (indexed by
j
) from the next element (i.e.,i+1
) to the last element of the array. - For each pair of elements
arr[i]
andarr[j]
, calculate their product:arr[i] * arr[j]
. - Check if the calculated product is equal to the target product. If it is, increment the counter by 1.
- Continue the nested loop until all pairs have been checked.
- Finally, return the value of the counter, which represents the number of pairs with the specified product.
Code Solution
//C Program
//Count all pairs of given product
#include <stdio.h>
//print the array elements
void display(int arr[], int size)
{
int i = 0;
for (i = 0; i < size; i++)
{
printf(" %d", arr[i]);
}
}
//Count all pairs of given product in array
void count_product(int arr[], int size, int product)
{
int counter = 0;
for (int i = 0; i < size; ++i)
{
for (int j = i + 1; j < size; ++j)
{
if (arr[i] * arr[j] == product)
{
//When get a new pair
counter++;
}
}
}
printf("\n Pair of product [%d] is : %d ", product, counter);
}
int main()
{
//Define array elements
int arr[] = {
5,
7,
4,
2,
-2,
-5,
10,
1,
20
};
//Count size of array
int size = sizeof(arr) / sizeof(arr[0]);
int product = 10;
printf("\n Array : ");
display(arr, size);
count_product(arr, size, product);
product = 40;
count_product(arr, size, product);
product = 60;
count_product(arr, size, product);
return 0;
}
Output
Array : 5 7 4 2 -2 -5 10 1 20
Pair of product [10] is : 3
Pair of product [40] is : 2
Pair of product [60] is : 0
// Java program
// Count all pairs of given product
class MyArray
{
//print the array elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; i++)
{
System.out.print(" " + arr[i]);
}
}
//Count all pairs of given product in array
public void count_product(int[] arr, int size, int product)
{
int counter = 0;
for (int i = 0; i < size; ++i)
{
for (int j = i + 1; j < size; ++j)
{
if (arr[i] * arr[j] == product)
{
//When get a new pair
counter++;
}
}
}
System.out.print("\n Pair of product [" + product + "] is : " + counter);
}
public static void main(String[] args)
{
MyArray obj = new MyArray();
//Define integer elements
int[] arr = {
5,
7,
4,
2,
-2,
-5,
10,
1,
20
};
//Count size of array
int size = arr.length;
int product = 10;
System.out.print("\n Array : ");
obj.display(arr, size);
obj.count_product(arr, size, product);
product = 40;
obj.count_product(arr, size, product);
product = 60;
obj.count_product(arr, size, product);
}
}
Output
Array : 5 7 4 2 -2 -5 10 1 20
Pair of product [10] is : 3
Pair of product [40] is : 2
Pair of product [60] is : 0
//Include header file
#include <iostream>
using namespace std;
// C++ program
// Count all pairs of given product
class MyArray
{
public:
//print the array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
cout << " " << arr[i];
}
}
//Count all pairs of given product in array
void count_product(int arr[], int size, int product)
{
int counter = 0;
for (int i = 0; i < size; ++i)
{
for (int j = i + 1; j < size; ++j)
{
if (arr[i] * arr[j] == product)
{
//When get a new pair
counter++;
}
}
}
cout << "\n Pair of product [" << product << "] is : " << counter;
}
};
int main()
{
MyArray obj = MyArray();
int arr[] = {
5 , 7 , 4 , 2 , -2 , -5 , 10 , 1 , 20
};
//Count size of array
int size = sizeof(arr) / sizeof(arr[0]);
int product = 10;
cout << "\n Array : ";
obj.display(arr, size);
obj.count_product(arr, size, product);
product = 40;
obj.count_product(arr, size, product);
product = 60;
obj.count_product(arr, size, product);
return 0;
}
Output
Array : 5 7 4 2 -2 -5 10 1 20
Pair of product [10] is : 3
Pair of product [40] is : 2
Pair of product [60] is : 0
//Include namespace system
using System;
// C# program
// Count all pairs of given product
class MyArray
{
//print the array elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; i++)
{
Console.Write(" " + arr[i]);
}
}
//Count all pairs of given product in array
public void count_product(int[] arr, int size, int product)
{
int counter = 0;
for (int i = 0; i < size; ++i)
{
for (int j = i + 1; j < size; ++j)
{
if (arr[i] * arr[j] == product)
{
//When get a new pair
counter++;
}
}
}
Console.Write("\n Pair of product [" + product + "] is : " + counter);
}
public static void Main(String[] args)
{
MyArray obj = new MyArray();
int[] arr = {
5 , 7 , 4 , 2 , -2 , -5 , 10 , 1 , 20
};
//Count size of array
int size = arr.Length;
int product = 10;
Console.Write("\n Array : ");
obj.display(arr, size);
obj.count_product(arr, size, product);
product = 40;
obj.count_product(arr, size, product);
product = 60;
obj.count_product(arr, size, product);
}
}
Output
Array : 5 7 4 2 -2 -5 10 1 20
Pair of product [10] is : 3
Pair of product [40] is : 2
Pair of product [60] is : 0
<?php
// Php program
// Count all pairs of given product
class MyArray
{
//print the array elements
public function display( & $arr, $size)
{
for ($i = 0; $i < $size; $i++)
{
echo " ". $arr[$i];
}
}
//Count all pairs of given product in array
public function count_product( & $arr, $size, $product)
{
$counter = 0;
for ($i = 0; $i < $size; ++$i)
{
for ($j = $i + 1; $j < $size; ++$j)
{
if ($arr[$i] * $arr[$j] == $product)
{
//When get a new pair
$counter++;
}
}
}
echo "\n Pair of product [". $product ."] is : ". $counter;
}
}
function main()
{
$obj = new MyArray();
//Define integer elements
$arr = array(5, 7, 4, 2, -2, -5, 10, 1, 20);
//Count size of array
$size = count($arr);
$product = 10;
echo "\n Array : ";
$obj->display($arr, $size);
$obj->count_product($arr, $size, $product);
$product = 40;
$obj->count_product($arr, $size, $product);
$product = 60;
$obj->count_product($arr, $size, $product);
}
main();
Output
Array : 5 7 4 2 -2 -5 10 1 20
Pair of product [10] is : 3
Pair of product [40] is : 2
Pair of product [60] is : 0
// Node Js program
// Count all pairs of given product
class MyArray
{
//print the array elements
display(arr, size)
{
for (var i = 0; i < size; i++)
{
process.stdout.write(" " + arr[i]);
}
}
//Count all pairs of given product in array
count_product(arr, size, product)
{
var counter = 0;
for (var i = 0; i < size; ++i)
{
for (var j = i + 1; j < size; ++j)
{
if (arr[i] * arr[j] == product)
{
//When get a new pair
counter++;
}
}
}
process.stdout.write("\n Pair of product [" + product + "] is : " + counter);
}
}
function main()
{
var obj = new MyArray();
//Define integer elements
var arr = [5, 7, 4, 2, -2, -5, 10, 1, 20];
//Count size of array
var size = arr.length;
var product = 10;
process.stdout.write("\n Array : ");
obj.display(arr, size);
obj.count_product(arr, size, product);
product = 40;
obj.count_product(arr, size, product);
product = 60;
obj.count_product(arr, size, product);
}
main();
Output
Array : 5 7 4 2 -2 -5 10 1 20
Pair of product [10] is : 3
Pair of product [40] is : 2
Pair of product [60] is : 0
# Python 3 program
# Count all pairs of given product
class MyArray :
# print the array elements
def display(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1
# Count all pairs of given product in array
def count_product(self, arr, size, product) :
counter = 0
i = 0
while (i < size) :
j = i + 1
while (j < size) :
if (arr[i] * arr[j] == product) :
# When get a new pair
counter += 1
j += 1
i += 1
print("\n Pair of product [", product ,"] is : ", counter, end = "")
def main() :
obj = MyArray()
# Define integer elements
arr = [5, 7, 4, 2, -2, -5, 10, 1, 20]
# Count size of array
size = len(arr)
product = 10
print("\n Array : ", end = "")
obj.display(arr, size)
obj.count_product(arr, size, product)
product = 40
obj.count_product(arr, size, product)
product = 60
obj.count_product(arr, size, product)
if __name__ == "__main__": main()
Output
Array : 5 7 4 2 -2 -5 10 1 20
Pair of product [ 10 ] is : 3
Pair of product [ 40 ] is : 2
Pair of product [ 60 ] is : 0
# Ruby program
# Count all pairs of given product
class MyArray
# print the array elements
def display(arr, size)
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end
end
# Count all pairs of given product in array
def count_product(arr, size, product)
counter = 0
i = 0
while (i < size)
j = i + 1
while (j < size)
if (arr[i] * arr[j] == product)
# When get a new pair
counter += 1
end
j += 1
end
i += 1
end
print("\n Pair of product [", product ,"] is : ", counter)
end
end
def main()
obj = MyArray.new()
# Define integer elements
arr = [5, 7, 4, 2, -2, -5, 10, 1, 20]
# Count size of array
size = arr.length
product = 10
print("\n Array : ")
obj.display(arr, size)
obj.count_product(arr, size, product)
product = 40
obj.count_product(arr, size, product)
product = 60
obj.count_product(arr, size, product)
end
main()
Output
Array : 5 7 4 2 -2 -5 10 1 20
Pair of product [10] is : 3
Pair of product [40] is : 2
Pair of product [60] is : 0
// Scala program
// Count all pairs of given product
class MyArray
{
//print the array elements
def display(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print(" " + arr(i));
i += 1;
}
}
//Count all pairs of given product in array
def count_product(arr: Array[Int], size: Int, product: Int): Unit = {
var counter: Int = 0;
var i: Int = 0;
while (i < size)
{
var j: Int = i + 1;
while (j < size)
{
if (arr(i) * arr(j) == product)
{
//When get a new pair
counter += 1;
}
j += 1;
}
i += 1;
}
print("\n Pair of product [" + product + "] is : " + counter);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyArray = new MyArray();
//Define integer elements
var arr: Array[Int] = Array(5, 7, 4, 2, -2, -5, 10, 1, 20);
//Count size of array
var size: Int = arr.length;
var product: Int = 10;
print("\n Array : ");
obj.display(arr, size);
obj.count_product(arr, size, product);
product = 40;
obj.count_product(arr, size, product);
product = 60;
obj.count_product(arr, size, product);
}
}
Output
Array : 5 7 4 2 -2 -5 10 1 20
Pair of product [10] is : 3
Pair of product [40] is : 2
Pair of product [60] is : 0
// Swift program
// Count all pairs of given product
class MyArray
{
//print the array elements
func display(_ arr: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print(" ", arr[i], terminator: "");
i += 1;
}
}
//Count all pairs of given product in array
func count_product(_ arr: [Int], _ size: Int, _ product: Int)
{
var counter: Int = 0;
var i: Int = 0;
while (i < size)
{
var j: Int = i + 1;
while (j < size)
{
if (arr[i] * arr[j] == product)
{
//When get a new pair
counter += 1;
}
j += 1;
}
i += 1;
}
print("\n Pair of product [", product ,"] is : ", counter, terminator: "");
}
}
func main()
{
let obj: MyArray = MyArray();
//Define integer elements
let arr: [Int] = [5, 7, 4, 2, -2, -5, 10, 1, 20];
//Count size of array
let size: Int = arr.count;
var product: Int = 10;
print("\n Array : ", terminator: "");
obj.display(arr, size);
obj.count_product(arr, size, product);
product = 40;
obj.count_product(arr, size, product);
product = 60;
obj.count_product(arr, size, product);
}
main();
Output
Array : 5 7 4 2 -2 -5 10 1 20
Pair of product [ 10 ] is : 3
Pair of product [ 40 ] is : 2
Pair of product [ 60 ] is : 0
Time Complexity
The time complexity of the provided code is O(n^2), where 'n' is the size of the input array. This is because we use nested loops to compare each pair of elements in the array, resulting in quadratic time complexity. As the size of the array increases, the execution time will grow quadratically.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment