C++ Tutorial Index

C++ Tutorial C++ History C++ Installation C++ First Program C++ cin and cout C++ Data type C++ Variable C++ operator C++ Keywords

C++ Control Statements

C++ If C++ Nested if C++ If-else C++ If-else-if C++ Switch C++ Break C++ Continue C++ Goto C++ For loop C++ While loop C++ Do while loop

C++ Functions

C++ Call by Value C++ Call by Reference C++ Recursion Function C++ Inline function C++ Friend function

C++ Arrays

Single dimension array Two dimension array

C++ Strings

C++ Strings

C++ Inheritance

C++ Inheritance Single level Inheritance Multilevel Inheritance Multiple Inheritance Hierarchical Inheritance Hybrid Inheritance

C++ Polymorphism

C++ Polymorphism C++ Overloading C++ Overriding C++ Virtual Function

C++ Pointers

C++ Pointers C++ this pointer

C++ Exception Handling

C++ Exception Handling

C++ Constructors

C++ Constructors Default Constructor Parameterize Constructor Copy constructor Constructor Overloading Destructor

C++ File Handling

C++ File Handling C++ Writing to file C++ Reading file C++ Close file

Miscellaneous

C Vs C++ C++ Comments C++ Data Abstraction C++ Identifier C++ Memory Management C++ Storage Classes C++ Void Pointer C++ Array To Function C++ Expressions C++ Features C++ Interfaces C++ Encapsulation std::min in C++ External merge sort in C++ Remove duplicates from sorted array in C++ Precision of floating point numbers Using these functions floor(), ceil(), trunc(), round() and setprecision() in C++ C++ References C++ Friend Functions C++ Mutable keyword Unary Operators in C++ Initialize Array of objects with parameterized constructors in C++ Differences between #define & const in C/C++ C++ Program to Implement Shell Sort C++ Program to Implement Merge Sort Storage Classes in C Vector resize() in C++ Passing by Reference Vs. Passing by the pointer in C++ Free vs delete() in C++ goto statement in C and C++ C++ program to read string using cin.getline() C++ String Concatenation Heap Sort in C++ Swap numbers in C++ Input Iterators in C++ Fibonacci Series in C++ C ++ Program: Alphabet Triangle and Number Triangle C++ Program: Matrix Multiplication C++ Program to Print Fibonacci Triangle Stack in C++ Maps in C++ Queue in C++ C++ Bitset C++ Algorithms Priority Queue in C++ C++ Multimap C++ Deque Function Pointer in C++ Sizeof() Operators in C++ C++ array of Pointers free() Vs delete in C Timsort Implementation Using C++ CPP Templates C++ Aggregation C++ Enumeration C++ Math Functions C++ Object Class C++ Queue Initialize Vector in C++ Vector in C++ C++ STL Components Function overloading in C++ C++ Maximum Index Problem C++ find missing in the second array C++ Program to find the product array puzzle C++ Program To Find Largest Subarray With 0 Sum C++ Program To Move All Zeros To The End Of The Array C++ Program to find the element that occurs once C++ Program to find the largest number formed from an array Constructor Vs Destructor C++ Namespaces C++ OOPs Concept C++ Static C++ Structs C++ Try-Catch C++ User Defined Exceptions C++ Virtual Destructor C++ vs C# Malloc() and new in C++ Palindrome Number Program in C++ Snake Code in C++ Splitting a string in C++ Structure Vs Class in C++ Virtual Function Vs Pure Virtual Function C++ Bidirectional Iterators C++ Forward Iterators C++ Iterators C++ Output Iterators C++ Range-based For Loop Converting string into integer in C++ LCM Program in C++ Type conversion in C++ Add two numbers using the function in C++ Advantage and disadvantage friend function C++ Armstrong Number Program in C++ ATM machine program in C++ using functions Binary to Decimal in C++ Bit Manipulation in C++ C++ Constructor C++ Dijkstra Algorithm Using the Priority Queue C++ int into String C++ Signal Handling Decimal to Binary in C++ Decimal to Hexadecimal in C++ Decimal to Octal in C++ Factorial Program in C++ Function in C++ Hexadecimal to Decimal in C++ Octal to Decimal in C++ Reverse a Number in C++ Structure Vs Class in C++ C++ Forward Iterators C++ Output Iterators C++ Prime number program Char Array to String in C++ Constructor Overloading in C++ Default arguments in C++ Different Ways to Compare Strings in C++ Dynamic Binding in C++ Program to convert infix to postfix expression in C++ SET Data Structure in C++ Upcasting and Downcasting in C++ Reverse an Array in C++ Fast Input and Output in C++ Delete Operator in C++ Copy elision in C++ C++ Date and Time C++ Bitwise XOR Operator Array of sets in C++ Binary Operator Overloading in C++ Binary Search in C++ Implementing the sets without C++ STL containers Scope Resolution Operator in C++ Smart pointers in C++ Types of polymorphism in C++ Exception Handling in C++ vs Java Const Keyword in C++ Type Casting in C++ Static keyword in C++ vs Java Inheritance in C++ vs Java How to concatenate two strings in C++ Programs to Print Pyramid Patterns in C++ swap() function in C++ Structure of C++ Program Stringstream in C++ and its applications rand() and srand() in C / C++ C++ Ternary Operator C++ Scope of Variables While Loop Examples in C++ Star pattern in C++ using For Loops For Loop Examples in C++ Do-While Loop Examples in C++ Top 5 IDEs for C++ That You Should Try Once Assertions in C/C++ C++ Convert Int to String Continue in C++ While loop Diamond Pattern in C++ using For Loop How to Reverse a String in C++ using Do-While Loop How to Reverse a String in C++ using For Loop How to Reverse a String in C++ using While Loop Infinite loop in C++ Loops in C++ Returning Multiple Values from a Function using Tuple and Pair in C++ wcscpy(), wcslen(), wcscmp() Functions in C++

C++ Program to find the product array puzzle

Write a C++ program to form a product array from arr[] where product[i] is the product of all the array elements except arr[i].

Example

Input: arr[]  = {10, 3, 5, 6, 2}

Output: prod[]  = {180, 600, 360, 300, 900}

Prod[0] = 3 * 5 * 6 * 2 product of other array elements except 10 is 180

Prod[1] = 10 * 5 * 6 * 2 product of other array elements except 3 is 600

Prod[2] = 10 * 3 * 6 * 2 product of other array elements except 5 is 360

Prod[3] = 10 * 3 * 5 * 2 product of other array elements except 6 is 300

Prod[4] = 10 * 3 * 6 * 5 product of other array elements except 2 is 900

Input: arr[]  = {1, 2, 3, 4, 5}

Output: prod[]  = {120, 60, 40, 30, 24 }

Prod[0] =2 * 3 * 4 * 5  product of other array elements except 1 is 120

Prod[1] =1 * 3 * 4 * 5  product of other array elements except 2 is 60

Prod[2] =1 * 2 * 4 * 5  product of other array elements except 3 is 40

Prod[3] =1 * 2 * 3 * 5  product of other array elements except 4 is 30

Prod[4] =1 * 2 * 3 * 4  product of other array elements except 5 is 24

Brute force approach

Create two arrays left[] and right[] in such a way that -

  • Left[] - stores the product of the array elements from the start to that index.
  • Right[] - stores the product of the array from the last to that index.

Now, to get the product array we multiply the left product upto i-1 and the right product to i+1. This will exclude the current ith element that is also the requirement.

Algorithm

  • Create three arrays - left, right, and product.
  • Iterate from 0 to n and update left as

left[i] = arr[i - 1] * left[i - 1]

  • Update the right array as by running the loop from n-1 to 0

right[j] = arr[j + 1] * right[j + 1]

  • Run a loop from 0 to n and update the prod array by multiplying the left and right array.

prod[i] = left[i] * right[i]

  • Print the prod array.

C++ code

#include <bits/stdc++.h>

using namespace std;

void productArray(int arr[], int n) // function to find the product array

{


          // if the array size is 1 no product array  can be formed

          if (n == 1) {

                   cout << 0;

                   return;

          }

          // make the left and right array

          int* left = new int[sizeof(int) * n];

          int* right = new int[sizeof(int) * n];


          // make the resultant product array

          int* prod = new int[sizeof(int) * n];


          int i, j;

          // as left will be multiplied with other indicies the first product is 1

          left[0] = 1;

// as right will also be multiplied with other indicies the last product is 1

          right[n - 1] = 1;


// fill the left array

          for (i = 1; i < n; i++)

                   left[i] = arr[i - 1] * left[i - 1];


          // fill the right array

          for (j = n - 2; j >= 0; j--)

                   right[j] = arr[j + 1] * right[j + 1];


// multiply left and right to form product array

          for (i = 0; i < n; i++)

                   prod[i] = left[i] * right[i];


// print the formed product array

          for (i = 0; i < n; i++)

                   cout << prod[i] << " ";




          return;

}




int main()

{

          int arr[] = { 10, 3, 5, 6, 2 };

          int n = sizeof(arr) / sizeof(arr[0]); // find size of araay

          cout << "The resultant array: \n";

          productArray(arr, n);

}

Output

The resultant array:

180 600 360 300 900

C code

#include <stdio.h>

#include <stdlib.h>

void productArray(int arr[], int n) // function to find the product array

{




          // if the array size is 1 no product array  can be formed

          if (n == 1) {

                   printf("0") ;

                   return;

          }

          // make the left and right array

int* left = (int*)malloc(sizeof(int) * n);

    int* right = (int*)malloc( sizeof(int) * n);










          // make the resultant product array

   int* prod = (int*)malloc(sizeof(int) * n);




          int i, j;




          // as left will be multiplied with other indicies the first product is 1

          left[0] = 1;




// as right will also be multiplied with other indicies the last product is 1

          right[n - 1] = 1;




// fill the left array

          for (i = 1; i < n; i++)

                   left[i] = arr[i - 1] * left[i - 1];




          // fill the right array

          for (j = n - 2; j >= 0; j--)

                   right[j] = arr[j + 1] * right[j + 1];




// multiply left and right to form product array

          for (i = 0; i < n; i++)

                   prod[i] = left[i] * right[i];




// print the formed product array

          for (i = 0; i < n; i++)

                   printf("%d ",prod[i]);




          return;

}




int main()

{

          int arr[] = { 10, 3, 5, 6, 2 };

          int n = sizeof(arr) / sizeof(arr[0]); // find size of araay

          printf( "The resultant array: \n");

          productArray(arr, n);

}

Output

The resultant array:

180 600 360 300 900

Time complexity - O(n)

Space complexity - O(n)

Efficient solution

In the previous approach, we created left and right arrays. So, here we will minimise the space by only using the product array itself.

  • Create a prod array with all the indices as value 1.
  • Create a temp variable and set its value to 1
  • For every index, update prod[i] to temp and then update temp by

temp = temp * prod[i]

  • Repeat the above step by iterating from last to 0. Now, set

prod[i]* = temp and then temp* = arr[i]

  • Print the prod array.

C++ code

#include <bits/stdc++.h>

using namespace std;




void productArray(int arr[], int n)

{

          // if the array size is 1 no product array  can be formed

          if (n == 1) {

                   cout << 0;

                   return;

          }

int i, temp = 1;




    int* prod = new int[(sizeof(int) * n)]; // Allocate resultant prod array




   

    memset(prod, 1, n); // set all values in prod array as 1




    /* In this loop, temp variable contains product of

       elements on left side excluding arr[i] */

    for (i = 0; i < n; i++) {

        prod[i] = temp;

        temp *= arr[i];

    }




    //Initialize temp to 1for product on right side

    temp = 1;




    //In this loop, temp variable contains product of

      // elements on right side excluding arr[i]

    for (i = n - 1; i >= 0; i--) {

        prod[i] *= temp;

        temp *= arr[i];

    }




    // print prod array

    for (i = 0; i < n; i++)

        cout << prod[i] << " ";




    return;




}




int main()

{

          int arr[] = { 10, 3, 5, 6, 2 };

          int n = sizeof(arr) / sizeof(arr[0]); // find size of araay

    cout <<  "The resultant array: \n";

          productArray(arr, n);

}

Output

The resultant array:

180 600 360 300 900

C code

#include <stdio.h>

#include <stdlib.h>

void productArray(int arr[], int n)

{

          // if the array size is 1 no product array  can be formed

          if (n == 1) {

                   printf("0");

                   return;

          }

int i, temp = 1;




          // make the resultant product array

   int* prod = (int*)malloc(sizeof(int) * n);

    memset(prod, 1, n); // set all values in prod array as 1

    /* In this loop, temp variable contains product of

       elements on left side excluding arr[i] */

    for (i = 0; i < n; i++) {

        prod[i] = temp;

        temp *= arr[i];

    }




    //Initialize temp to 1for product on right side

    temp = 1;




    //In this loop, temp variable contains product of

      // elements on right side excluding arr[i]

    for (i = n - 1; i >= 0; i--) {

        prod[i] *= temp;

        temp *= arr[i];

    }




    // print prod array

    for (i = 0; i < n; i++)

        printf("%d ",prod[i]);




    return;




}




int main()

{

          int arr[] = { 10, 3, 5, 6, 2 };

          int n = sizeof(arr) / sizeof(arr[0]); // find size of araay

    printf( "The resultant array: \n");

          productArray(arr, n);

}

Output

The resultant array:

180 600 360 300 900

Another approach

The approach first takes the product of the whole array variables. After that iterate in the array and update the index of arr[i] as

                                      arr[i] = prod/arr[i]

And then return the new array.

C++ code

#include <iostream>

using namespace std;




void productArray(int a[], int n)

{

          long prod = 1; // the product is assigned as 1

          long flag = 0; // to track 0's in the array




          // Calculate the product of all elements

          for (int i = 0; i < n; i++) {




                   if (a[i] == 0) // increment flag if there is any 0

                             flag++;

                   else

                             prod *= a[i]; // calculate prod

          }




          long* arr = new long[n]; // create resultant arr




          for (int i = 0; i < n; i++) {







                   if (flag > 1) { // if the count of flag is > 0 then

                             arr[i] = 0; // all element in array are 0

                   }




                   else if (flag == 0) // if no zero encountered in arr[i]

                             arr[i] = (prod / a[i]);




                   // if 1 element of array having

                   // value 0 than all

                   // the elements except that index

                   // value , will be

                   // equal to 0

                   else if (flag == 1 && a[i] != 0) {

                             arr[i] = 0;

                   }




                   // if(flag == 1 && a[i] == 0)

                   else

                             arr[i] = prod;

          }

          for(int i=0;i<n;i++)

          cout << arr[i] << " ";

}




int main()

{

          int arr[] = { 10, 3, 5, 6, 2 };

          int n = sizeof(arr) / sizeof(arr[0]); // find size of araay

    printf( "The resultant array: \n");

          productArray(arr, n);

}

Output

The resultant array:

180 600 360 300 900

C code

#include <stdio.h>

#include <stdlib.h>

void productArray(int a[], int n)

{

         

          long prod = 1; // the product is assigned as 1

          long flag = 0; // to track 0's in the array




          // Calculate the product of all elements

          for (int i = 0; i < n; i++) {




                   if (a[i] == 0) // increment flag if there is any 0

                             flag++;

                   else

                             prod *= a[i]; // calculate prod

          }




          // make the resultant product array

   long* arr = (long*)malloc(sizeof(long) * n);







          for (int i = 0; i < n; i++) {







                   if (flag > 1) { // if the count of flag is > 0 then

                             arr[i] = 0; // all element in array are 0

                   }




                   else if (flag == 0) // if no zero encountered in arr[i]

                             arr[i] = (prod / a[i]);




                   // if 1 element of array having

                   // value 0 than all

                   // the elements except that index

                   // value , will be

                   // equal to 0

                   else if (flag == 1 && a[i] != 0) {

                             arr[i] = 0;

                   }




                   // if(flag == 1 && a[i] == 0)

                   else

                             arr[i] = prod;

          }

          for(int i=0;i<n;i++)

          printf("%d ", arr[i]);

}




int main()

{

          int arr[] = { 10, 3, 5, 6, 2 };

          int n = sizeof(arr) / sizeof(arr[0]); // find size of araay

    printf( "The resultant array: \n");

          productArray(arr, n);

}

Output

The resultant array:

180 600 360 300 900



ADVERTISEMENT
ADVERTISEMENT