### Create one array from another array array lineartime general    Posted: 5 years ago Edit answers (1) views (1262)

Suppose you are given an integer array. Design a linear time algorithm to create another integer array and populate it such that the second array's $$i^{th}$$ position should be a product of all numbers from the first array excluding the number at the $$i^{th}$$ position. Note : You can't use division operator.

 Posted: 5 years ago Updated: 5 years ago 0 0 Edit The algorithm works as : Create two integer arrays, $$array1$$ and $$array2$$. $$array1$$ contains the running product of the numbers of the original array, $$i.e$$, $$i^{th}$$ element in $$array1$$ will be the product of the elements from position $$0$$ to $$i$$ in the original array. $$array2$$ works in the reverse direction as of $$array1$$, $$i.e$$, $$i^{th}$$ element in $$array2$$ will be the product of the elements from position $$n-i$$ to $$n$$ in the original array. The final resultant array can be constructed from $$array1$$ and $$array2$$. The $$i^{th}$$ element of the final array will be the product of $$array1[i-1]$$ and $$array2[i+1]$$. Example - Time complexity = $$O(n)$$, space complexity = $$O(n)$$.public void CreateArrayFromArray(int[] array){ /* Number of elements in the array */ int n = array.length; /* Create and populate array1 */ int k = 1; for(i = 0; i < n; i++){ k = k * array[i]; array1[i] = k; } /* Create and populate array2 */ int k = 1; for(i = n-1; i >= 0; i--){ k = k * array[i]; array2[i] = k; } /* final result in int[] array*/ /* Corner case - first element */ array[0] = array2[1]; for(i = 1; i < n-1; i--) array[i] = array2[i+1] * array1[i-1]; /* Corner case - last element */ array[n-1] = array1[n-2];}