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.

1. For a product of 10, there are 3 pairs that meet this condition:

   • (5, 2)
   • (-2, -5)
   • (10, 1)

2. For a product of 40, there are 2 pairs:

   • (5, 8)
   • (2, 20)

3. 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:

1. Iterate through the array using a nested loop to consider each pair of elements.
2. For each pair, calculate their product.
3. Compare the calculated product with the target product.
4. 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:

1. Initialize a counter to zero, which will keep track of the number of pairs that meet the condition.
2. 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.
3. 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.
4. For each pair of elements arr[i] and arr[j], calculate their product: arr[i] * arr[j].
5. Check if the calculated product is equal to the target product. If it is, increment the counter by 1.
6. Continue the nested loop until all pairs have been checked.
7. Finally, return the value of the counter, which represents the number of pairs with the specified product.

Code Solution

• C
• Java
• C++
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4

//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;
}

  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);
	}
}

 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;
}

 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);
	}
}

 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();

 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();

 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()

 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()

 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);
	}
}

 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();

 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.