Product of All Other Numbers in Array - Coding in A Smart Way

Product of All Other Numbers in Array - Coding in A Smart Way

Written by truongkhanh on Problem: Product of All Other Numbers in Array Given an array A of integer number, compute array B such that B[i] = ∏A[j] where j  ≠  i. For example, if A = [2, 8, 7, 5], then B = [8x7x5=280, 2x7x5=70, 2x8x5=80, 2x8x7=112]. What if you can not use division (/) operator. Discussion A naive solution is that we compute B[i] separately. Given any i, we loop through the array A and compute ∏A[j] where j  ≠  i. Then the complexity is O(N) where N is the number of array A. Therefore, it takes O(N2) to compute B. For example, B[0] = 8x7x5, B[1] = 2x7x5, etc. We note that there are many redundant computing, for example 7×5. Actually, we can compute B[i] more efficient by using formula B[i] = P / A[i] where P is the product of all elements in A. Thus, we just compute P once and use for all computing. The complexity is thus O(N). public static int[] productOfOtherNumbers(int [] A) { int product = 1; for (int a : A) { product *= a; } int[] result = new int[A.length];

Read full article from Product of All Other Numbers in Array - Coding in A Smart Way