The sum of the products of each pair

The pairwise product of the set X = {a, b, c} can be defined as the sum of the products of all possible set pairs. The pairs of sets are Y = {a * a, a * b, a *c, b * b, b * c, c * c}, where the products are commutative. Therefore, the pairwise product of a set X is the sum of the elements of the set Y, which is aa ab ac bb bc cc.

In mathematical terms, the sum of possible pairwise products can be expressed as:

$$\mathrm{\displaystyle\sum\limits_{i=1,j=i}^{i\leq n,j\leq n}\:(i,j)=i\time j}$$

Problem Statement

Given a number n. Find the sum of pairwise products in the range (1, n), inclusive of n and 1.

Example Example 1

Input: n = 4

Output: 65

Explanation

Explanation

i ranges from 1 to 4, j ranges from i to 4.

1*1 1*2 1*3 1*4 2*2 2*3 2*4 3*3 3*4 4*4 = 1 2 3 4 4 6 8 9 12 16 = 65

Example Example 2

Input: n = 10

Output: 1705

Explanation

Explanation

i ranges from 1 to 10, j ranges from i to 10.

1*1 1*2 … 1*10 2*2 2*3 … 2*10 3*3 3*4 … 3*10 4*4 4 *5 … 4*10 5*5 5*6 … 5*10 6*6 6*7 … 6*10 7*7 7*8 … 7*10 8* 8 8*9 8*10 9*9 9*10 10*10 = 1705

Method 1: Brute force cracking method

The brute force solution to this problem is to use two for loops to iterate all possible pairs of numbers in the range, where the first loop iterates from 1 to n and the second loop iterates from the first number to n.

pseudocode

procedure pairwiseProduct (n) sum = 0 for i = 1 to n for j = i to n sum = sum + (i * j) end procedure

Example: C implementation

In the following program, we find all possible pairs and then find the sum of the products.

#include  using namespace std; // Function to find pairwise product over the range 1 to n, 1 and n inclusive unsigned long long pairwiseProduct(unsigned int n){ unsigned long long sum = 0; // First number: 1 <= i <= n for (unsigned int i = 1; i <= n; i++){ // Second number: i <= j <= n for (unsigned int j = i; j <= n; j++){ sum += i * j; } } return sum; } int main(){ unsigned long long n = 9; cout << "Pairwise Product = " << pairwiseProduct(n); return 0; }

Output

Pairwise Product = 1155

Time complexity - O(n^2)

Space complexity - O(1)

Method Two

Take n = 4 as an example,

I = 1*1 1*2 1*3 1*4 2*2 2*3 2*4 3*3 3*4 4*4

In simplifying the above,

I = 1*1 (1 2)*2 (1 2 3)*3 (1 2 3 4)*4

Take prefix_sum[1] = 1,

Prefix sum[2] = 1 2,

Prefix sum[3] = 1 2 3,

Prefix sum[2] = 1 2,

pseudocode

procedure pairwiseProduct (n) sum = 0 prefixSum = 0 for i = 1 to n prefixSum = prefixSum + 1 sum = sum + i * prefixSum end procedure

Example: C implementation

In the program below, we find the sum of each iteration, the prefix sum, and multiply it by the number of iterations, then add to the final sum at each step.

#include  using namespace std; // Function to find pairwise product over the range 1 to n, 1 and n inclusive unsigned long long pairwiseProduct(unsigned int n){ unsigned long long sum = 0; unsigned long long prefixSum = 0; for (unsigned int i = 1; i <= n; i++){ prefixSum += i; sum += i * prefixSum; } return sum; } int main(){ unsigned long long n = 9; cout << "Pairwise Product = " << pairwiseProduct(n); return 0; }

Output

Pairwise Product = 1155

in conclusion

In short, to solve the sum of the products of pairs of numbers in the range 1 to n, we can use one of the two methods mentioned above. The first method is the brute force method, and the time complexity is O(n^ 2), the second method is an optimization method that uses prefix sum to calculate the sum of pairwise products, and the time complexity is O(n).

The above is the detailed content of The sum of the products of each pair. For more information, please follow other related articles on the PHP Chinese website!