Find product of every integer except integer at that index

Find product of every integer except integer at that index

This one is also popular question to check candidate ability to write algorithm quick within an hour during first round of screening interview.

Question: You have a list of integers, and for each index you want to find the product of every integer except the integer at that index.
Write a function get_products_of_all_ints_except_at_index() that takes a list of integers and returns a list of the products.

For example, given:

[1, 7, 3, 4]

your function would return:

[84, 12, 28, 21]

by calculating:

[7*3*4, 1*3*4, 1*7*4, 1*7*3]

Simple solution:

package com.javahonk.test;

import java.util.ArrayList;
import java.util.List;

public class FindIntArrayProduct {
	
	public static void main(String[] args) {
		
		int[] array = { 1, 7, 3, 4};
		List<Integer> product  = new ArrayList<Integer>();
		
		for (int i = 0; i < array.length; i++) {
			int multiplication =1;
			for (int j = 0; j < array.length; j++) {
				int skipValue = array[i];
				if (skipValue != array[j]) {
					multiplication = multiplication*array[j];
				}
			}			
			product.add(multiplication);
		}
		
		System.out.println(product);
		
	}

}

Another solution: While there are many ways you could do this I found below two ways to do it:

• FindIntArrayProduct.java:

package com.intarrayindex;

import java.util.Arrays;

public class FindIntArrayProduct {

	public static void main(String[] args) {		
		
		int[] array = { 1, 7, 3, 4};
		
		usingO_n_SquareAlgorithm(array);		
		usingO_n_Algorithm(array);

	}

	//This method is using O(n2) time because we have two for loop
	private static void usingO_n_SquareAlgorithm(int[] array) {
		
		int[] productOfIntegers = new int[array.length];

		for (int i = 0;  i < array.length;  i++)
		{
		    productOfIntegers[i] = 1;			
			
		    for (int j = 0;  j < array.length;  j++)
		        if (j != i) // Exclude current index
		            productOfIntegers[i] *= array[j];
		}
		
		System.out.println(Arrays.toString(productOfIntegers));
	}
	
	//This method is using O(n) time
	private static void usingO_n_Algorithm(int array[]){
		
		int[] newArray = new int[array.length];
		
		int product = 1;
	    
		for (int i=0; i < array.length; i++) {
	    	product = product * array[i];	    	
	    }

	    for (int i=0; i < array.length; i++) {
	    	newArray[i] = product / array[i];
			System.out.print(newArray[i] + " ");
	    }
	}

}

• Output:

Reference:

• Java Arrays