- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

In this problem, we are given an integer n which is the number of elements. Our task is to create a program that counts the number of ways to multiply n elements with the associative operation.

**Associative operations** return the same result irrespective of the manner the numbers are arranged.

Let’s take an example to understand the problem,

3

12

(x*(y*z)), (x*(z*y)), (y*(x*z)), (y*(z*x)), (z*(x*y)), (z*(y*x)), ((x*y)*z), ((y*x)*z), ((x*z)*y), ((z*x)*y), ((z*y)*x), ((y*z)*x).

To solve this problem, we will try to find if there is any relation or any type of series that can be created so that we can generalize our results. Let’s see the number of associative operations based on the number of operators −

1 => 1 2 => 2 3 => 12

Now, let’s try to generalize the count. Let’s suppose, we are creating associative operations for n elements then, we can place n-1 multiply operators and n-1 parenthesis.

Here, we will arrange them in two ways −

Considering ways to multiply till (

**n-1**). And then we can insert the last element an at any of the ends of the association. This can for n-1 numbers will from 2*2*(n-2) associations for n operators.Then we will consider multiplication of (a1, a2, … a(n-1)) and multiple an to left or right which gives additional two ways to create associations.

Let’s add and get the total associations for n operators using the above case.

ass(n) = ((2*2*(n-2))(ass(n-1))) + 2*(ass(n-1)) ass(n) = (4n-8)(ass(n-1)) + 2*(ass(n-1)) ass(n) = (4n-6)(ass(n-1))

This relation is the same as pseudo Catalan Number, which has the same formula and same initials values.

So, we can apply the general formula for pseudo Catalan Number here,

ass(n) = (2*n-2)!/(n-1)!

Let’s see the working of our formula for values n = 5.

ass(10) = (2*5 - 2)!/ (5-1)! ass(10) = 8!/4! = 40320/24 = 1680

**Program to find the Ways to multiply n elements with an associative operation**

// Program to find the Ways to multiply n elements with an associative operation −

#include<iostream> using namespace std; long int calcFactorial(int n){ if (n == 0 || n == 1) return 1 ; return n*calcFactorial(n-1); } long int calcWays ( int n ){ int N = 2*n - 2 ; int R = n - 1 ; return (calcFactorial((2*n)-2)/calcFactorial(n-1)); } int main(){ int n = 7; cout<<"The ways to multiply "<<n<<" elements with an associative operation : "<<calcWays(n); return 0 ; }

The ways to multiply 7 elements with an associative operation : 665280

- Related Questions & Answers
- Ways to sum to N using array elements with repetition allowed in C++
- Creating an associative array in JavaScript with push()?
- Multiply Adjacent elements in Python
- JavaScript in filter an associative array with another array
- Associative arrays in C++
- Find the Number of Ways to Traverse an N-ary Tree using C++
- Remove duplicated elements of associative array in PHP
- Creating an associative array in JavaScript?
- PHP array_push() to create an associative array?
- Convert an object to associative array in PHP
- Minimum operation to make all elements equal in array in C++
- Number of Ways to Paint N × 3 Grid in C++
- How to multiply two matrices by elements in R?
- Query in MongoDB to perform an operation similar to LIKE operation
- Python program to find ways to get n rupees with given coins

Advertisements