Multiplication of Previous and Next


Difficulty Level Easy
Frequently asked in Accenture Accolite Adobe Factset UHG Optum
Array

Problem Statement

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.

Implementation

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;
}

Java Program for Multiplication of Previous and Next

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int prev=arr[0],temp; // previous element to be stored so that no extra space is used.
        arr[0]=arr[0]*arr[1];
        System.out.print(arr[0]+"  ");
        for(int i=1;i<n-1;i++)
        {
          temp=prev;
          prev=arr[i];//set previous to this element
          arr[i]=arr[i+1]*temp; // multiply prev and forward element
          System.out.print(arr[i]+"  ");
        }
        arr[n-1]=arr[n-1]*prev;
        System.out.println(arr[n-1]);
    }
}
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