search
HomeBackend DevelopmentC++The sum of the products of each pair

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
The Chinese translation of

Explanation

is:

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
The Chinese translation of

Explanation

is:

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 <bits/stdc++.h>
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 <bits/stdc++.h>
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!

Statement
This article is reproduced at:tutorialspoint. If there is any infringement, please contact admin@php.cn delete
How to implement loosely coupled design in C?How to implement loosely coupled design in C?Apr 28, 2025 pm 09:42 PM

To implement loose coupling design in C, you can use the following methods: 1. Use interfaces, such as defining the Logger interface and implementing FileLogger and ConsoleLogger; 2. Dependency injection, such as the DataAccess class receives Database pointers through the constructor; 3. Observer mode, such as the Subject class notifies ConcreteObserver and AnotherObserver. Through these technologies, dependencies between modules can be reduced and code maintainability and flexibility can be improved.

What is exception neutral code in C?What is exception neutral code in C?Apr 28, 2025 pm 09:39 PM

Exception-neutral code refers to a snippet of code that neither throws nor handles exceptions. In C programming, applying exception neutral code can simplify exception handling logic and improve code maintainability and reliability.

How to use templates in C?How to use templates in C?Apr 28, 2025 pm 09:21 PM

C templates are used to implement generic programming, allowing for the writing of general code. 1) Define template functions, such as max functions, which are suitable for any type. 2) Create template classes, such as general container classes. 3) Pay attention to template instantiation, compilation time, template specialization, debugging and error information. 4) Follow best practices, keep the code simple, and consider using constraint template parameters.

How to implement lock-free data structure in C?How to implement lock-free data structure in C?Apr 28, 2025 pm 09:15 PM

Implementing lock-free data structures in C can be achieved by using atomic operations and CAS operations. The specific steps include: 1. Use std::atomic to ensure the atomic operation of head and tail; 2. Use compare_exchange_strong to perform CAS operations to ensure data consistency; 3. Use std::shared_ptr to manage node data to avoid memory leakage.

How to use string streams in C?How to use string streams in C?Apr 28, 2025 pm 09:12 PM

The main steps and precautions for using string streams in C are as follows: 1. Create an output string stream and convert data, such as converting integers into strings. 2. Apply to serialization of complex data structures, such as converting vector into strings. 3. Pay attention to performance issues and avoid frequent use of string streams when processing large amounts of data. You can consider using the append method of std::string. 4. Pay attention to memory management and avoid frequent creation and destruction of string stream objects. You can reuse or use std::stringstream.

What is static analysis in C?What is static analysis in C?Apr 28, 2025 pm 09:09 PM

The application of static analysis in C mainly includes discovering memory management problems, checking code logic errors, and improving code security. 1) Static analysis can identify problems such as memory leaks, double releases, and uninitialized pointers. 2) It can detect unused variables, dead code and logical contradictions. 3) Static analysis tools such as Coverity can detect buffer overflow, integer overflow and unsafe API calls to improve code security.

What is a memory stream in C?What is a memory stream in C?Apr 28, 2025 pm 09:03 PM

Memory streams in C refer to the technology that uses the std::stringstream, std::istringstream and std::ostringstream classes to read and write data in memory. 1) std::stringstream can be used for reading and writing, std::istringstream is used for reading, and std::ostringstream is used for writing. 2) Using memory streams can improve the performance of data processing, but you need to pay attention to the memory usage. 3) In order to improve the readability of the code, it is recommended to add detailed comments and documents.

What are package management tools in C?What are package management tools in C?Apr 28, 2025 pm 08:54 PM

C's package management tools mainly include the FetchContent of vcpkg, Conan and CMake. 1.vcpkg is suitable for large projects and multi-dependence scenarios, and is easy to use. 2.Conan emphasizes flexibility and customization, suitable for projects that require strict version control. 3. FetchContent is suitable for small projects and fast integration, and has relatively limited functions.

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

PhpStorm Mac version

PhpStorm Mac version

The latest (2018.2.1) professional PHP integrated development tool

SecLists

SecLists

SecLists is the ultimate security tester's companion. It is a collection of various types of lists that are frequently used during security assessments, all in one place. SecLists helps make security testing more efficient and productive by conveniently providing all the lists a security tester might need. List types include usernames, passwords, URLs, fuzzing payloads, sensitive data patterns, web shells, and more. The tester can simply pull this repository onto a new test machine and he will have access to every type of list he needs.

SublimeText3 English version

SublimeText3 English version

Recommended: Win version, supports code prompts!