Create one array from another array
  • Posted: 5 years ago
  • Edit
  • answers (1)
  • views (1161)

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 Answers

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

You need to Sign In to post your solution.