Home » Technical Interview Questions » Array Interview Questions » Multiplication of Previous and Next

Multiplication of Previous and Next


Multiplication of Previous and Next: In the given array replace every element with the product of next and previous elements to it. And for the first element(a[0]) we need to replace it with the product of next and itself, for  the last element(a[n-1]) we need to replace it with the product of previous and itself.)

Example

Input

9

4 8 6 9 12 2 43 2 1

Output

32 24 72 72 18 516 4 43 2

Algorithm for Multiplication of Previous and Next

Step 1: Create a variable to store the previous element of the array. we are storing this such that no extra space used.
a)    The first element will be the product of first and second.
b)    The next elements will be the product of the previous and next.

Step 2: Create a temp dummy variable to store the previous. after storing previous in temp, update previous with current element. after storing current in previous, update current element multiplying temp and next element of array.
a)    we are updating the previous element before updating current so, we store the value in temp so that we will not lose its value.
b)    we update previous with current element because for the next element it current is previous.

Step 3: The last element will be the product of the last and previous.

Step 4: print the array to see whether it is updated or not.

READ  All Unique Triplets that Sum up to a Given Value

C++ Program for Multiplication of Previous and Next

#include <bits/stdc++.h>
using namespace std;
int main()
{
  
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  int prev=a[0],temp; // previous element to be stored so that no extra space is used.
  a[0]=a[0]*a[1];
  cout<<a[0]<<"  ";
  for(int i=1;i<n-1;i++)
  {
    temp=prev;
    prev=a[i];//set previous to this element
    a[i]=a[i+1]*temp; // multiply prev and forward element
    cout<<a[i]<<"  ";
  }
  a[n-1]=a[n-1]*prev;
  cout<<a[n-1];
  return 0;
}
5
1 2 3 4 5
2  3  8  15  20

Complexity Analysis for Multiplication of Previous and Next

Time Complexity

O(n) where n is the length of the given array. Here we just iterate through the given array and compute our result which leads us to linear time complexity.

Space Complexity

O(1) because we use only a few variables to store the previous value and answer for each index.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Abhishek

Abhishek was able to crack Microsoft after practicing questions from TutorialCup