1
\$\begingroup\$

Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.

For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].

Is there a better solution for this problem?

Note: Division is not allowed.

public class DailyCodingProblem2 {
    public static void main(String args[]) {
        int[] arr = { 1, 2, 3, 4, 5 };
        int[] ans = solution(arr, arr.length);
        System.out.println(Arrays.toString(ans));

        arr = new int[] { 3, 2, 1 };
        ans = solution(arr, arr.length);
        System.out.println(Arrays.toString(ans));
    }

    private static int[] solution(int[] arr, int n) {
        int[] left = new int[n];
        int[] right = new int[n];
        int[] res = new int[n];
        left[0] = 1;
        right[n - 1] = 1;

        for (int i = 1; i < n; i++) {
            left[i] = arr[i - 1] * left[i - 1];
        }

        for (int i = n - 2; i >= 0; i--) {
            right[i] = arr[i + 1] * right[i + 1];
        }
        for (int i = 0; i < n; i++) {
            res[i] = left[i] * right[i];
        }
        return res;
    }
}
\$\endgroup\$
  • \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Mast Feb 1 at 11:42
  • \$\begingroup\$ "Note: Division is not allowed." Why? Is it because of a restriction for the assignment? \$\endgroup\$ – Solomon Ucko Feb 2 at 3:44
  • \$\begingroup\$ @SolomonUcko Yes it is a restriction for the assignment \$\endgroup\$ – Maclean Pinto Feb 4 at 5:15
2
\$\begingroup\$

Time complexity-wise, I think not. You're required to 'visit' all numbers, and your solution is O(n), so that can't be improved.

Code clarity could be improved, as it's not very obvious what the intention is. Some comments would help that. I think shifting indices by 1 might make it clearer (left[i+1] = arr[i] * left[i]), but then maybe not because it'd mess up the last loop.

Have you explored different algorithms? I wonder if straightforward memoization makes a very clear solution for this.

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.