Introduction

This tutorial will show you how to return array of products of all other numbers from a given array. Let’s say you are given an array of non-zero integers. So you have to return an output array of products of all other numbers except the number itself.

Example

For example, an input array a[]={1, 2, 3, 4}, so the output array will be out[]={24, 12, 8, 6}.

Therefore, if we analyze the above output array, then

at array index 0, the output is formulated as 2x3x4 = 24.

at array index 1, the output is formulated as 1x3x4 = 12.

at array index 2, the output is formulated as 1x2x4 = 8.

at array index 3, the output is formulated as 1x2x3 = 6.

Java Code

Let’s move on to the implementation of Java code to return array of products of all other numbers from a given array.

The implementation can be done in three ways with O(n) time complexity.

First Approach

In the multiply and divide approach we will multiply all elements in the array and finally divide by elements at array indices to get the desired output.

public class ArrayProductsDiv {
	public static void main(String[] args) {
		int[] a = new int[] { 1, 2, 3, 4 };
		int out[] = new int[4];
		int p = 1;
		for (int i = 0; i < a.length; ++i) {
			p *= a[i];
		}
		for (int i = a.length - 1; i >= 0; --i) {
			out[i] = p / a[i];
		}
		for (int i = 0; i < out.length; i++) {
			System.out.println(out[i]);
		}
	}
}

So in the above code we first calculate product for all numbers in the given array. And finally we divide product by each array element and get the desired output.

Second Approach

In the first approach we used division to find out the desired results but here we find out the desired results without division.

public class ArrayProductsNoDiv {
	public static void main(String[] args) {
		int[] a = new int[] { 1, 2, 3, 4 };
		int out[] = new int[4];
		int prod = 1;
		for (int i = 0; i < a.length; ++i) {
			out[i] = prod;
			prod *= a[i];
		}
		prod = 1;
		for (int i = a.length - 1; i >= 0; --i) {
			out[i] *= prod;
			prod *= a[i];
		}
		for (int i = 0; i < out.length; i++) {
			System.out.println(out[i]);
		}
	}
}

Third Approach

In this example we will see the recursive function to get the desired output:

public class ArrayProductsRecursive {
	public static void main(String[] args) {
		int[] a = new int[] { 1, 2, 3, 4 };
		product(a, 1, 0);
		for (int i = 0; i < a.length; i++) {
			System.out.println(a[i]);
		}
	}
	static int product(int[] a, int prod, int n) {
		return (n == a.length) ? 1 : a[n] * (prod = product(a, a[n] * (a[n] = prod), n + 1)) + 0 * (a[n] *= prod);
	}
}

You will find more solutions here https://stackoverflow.com/questions/2680548/given-an-array-of-numbers-return-array-of-products-of-all-other-numbers-no-div.

Thanks for reading.

Tags:

Leave a Reply

Your email address will not be published. Required fields are marked *