Array Product

Q: Given an unsorted array of I of N integers, find an array O of N integers such that O[i] is the product of all integers in I except I[i]. Solve without using division.

Soln approach: 
1. Break the product into two parts as O[i] = (I[0] * I[1] * ... * I[i-1]) * (I[i+1] * ... * I[N-1])

2. Calculate first part by iterating over I from 0 to N-1
3. Multiply the values from step 2 with the second part by iterating over I from N-1 to 0

Java code to do this:

	/**
	* Author: Varun
	* Date: June 3, 2012
	*/
	public class ArrayProduct {
	public int[] findProduct(int[] input) {
	if(input == null) return null;
	int[] output = new int[input.length];
	int prod = 1;
	for(int i = 0; i < input.length; i++) {
	output[i] = prod;
	prod = prod * input[i];
	}
	prod = 1;
	for(int i = input.length - 1; i >= 0; i--) {
	output[i] = output[i] * prod;
	prod = prod * input[i];
	}
	return output;
	}
	public static void main(String[] args) {
	int[] input = {13,9,65,72,12,99,8};
	ArrayProduct p = new ArrayProduct();
	int[] output = p.findProduct(input);
	System.out.print("The result is: ");
	for(int i = 0; i < output.length; i++) {
	System.out.print(output[i] + " ");
	}
	}
	}

view raw ArrayProduct.java hosted with ❤ by GitHub