3
\$\begingroup\$

I had the following interview question: Given an array of integers, for each member of the array find the product of all the other members of the array. So for instance, if you have this array:

{3, 1, 2, 0, 4}

you should end up with this:

{0 0 0 24 0}

I wrote this code which uses two loops, but I couldn't come up with a solution with just one loop. Can anyone help me?

public int[] findProducts(int[] arr) {
    int[] products = new int[arr.length];

    for (int i = 0; i < arr.length; i++) {
        int product = 1;

        for (int j = 0; j < arr.length; j++) {
            if (i != j) {
                product *= arr[j];
            }
        }

        products[i] = product;
    }

    return products;
}
\$\endgroup\$
  • \$\begingroup\$ Was your solution rejected because you used two nested loops? \$\endgroup\$ – TorbenPutkonen May 2 at 6:04
  • \$\begingroup\$ Well, the interviewer acknowledged that this situation would work, but he also asked if there was a more efficient way to do it, and I was at a loss, hence my bringing the problem here. \$\endgroup\$ – Frank May 2 at 17:35
2
\$\begingroup\$

This could be done with two consecutive loops (instead of nested loops), making it O(N) instead of O(N^2).

In the first loop you calculate the total product of all non-zero elements (and the number of zeros).

If there are more than one zero, return result as is, since all elements already default to zero.

In the second you either set the result element to zero or to total product divided by the current element depending on the number of zeros in the data and the value of the current element.

BTW, There are a lot of blog posts and even some research written about the pointlessness of this kind of interview questions.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the help. I would agree that this question does seem pretty pointless. How often does this kind of situation occur in a real-world application? \$\endgroup\$ – Frank May 2 at 17:34
  • \$\begingroup\$ @Frank Situations like these do occur, but the difference is that in real life nobody ever has to solve them in such a short and stressful scenario as job interview is. And in real life you're usually given more limitations (e.g. told that there will be a million entries instead of five so you're already prepared for writing the code with efficiency in mind) \$\endgroup\$ – TorbenPutkonen May 3 at 7:46
0
\$\begingroup\$

This could also be done using a single for loop in a recursive method that can calculate for each member of the array the product of all the other members of the array .

this can be done like this .

import java.util.Arrays;

public class ArrayElementsProduct {
    private int[] originalArray = {3, 1, 2, 0, 4};
    private int[] productsArray = {1, 1, 1, 1, 1};
    private int j = 0; // j is used to recursion the method product() only uptill the last element in productArray


    public static void main(String[] args) {
        new ArrayElementsProduct().product();//created an anonymous object of ArrayElementsProduct and calling method product() through it.
    }

    private void product() {
        for (int i = 0; i < originalArray.length; i++) {
            if (j != i) {
                productsArray[j] *= originalArray[i];//multiplying the originalArray elements and storing them in productArray
            }
        }
        j++;
        if (j < productsArray.length) {
            product();  //recursing the method product
        } else {
            System.out.println(Arrays.toString(productsArray));
        }
    }
}

Recursion basically works like a loop itself , this is just an idea that came in my mind for the question , i am just a beginner in Java .

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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