Skip to content

Instantly share code, notes, and snippets.

@mugizico
Created July 21, 2015 23:54
Show Gist options
  • Save mugizico/a6a87cc7faa2ed9ffdd7 to your computer and use it in GitHub Desktop.
Save mugizico/a6a87cc7faa2ed9ffdd7 to your computer and use it in GitHub Desktop.
Interview Cake #2 : Products of all integers at that index
/*
*You have an array of integers,
*and for each index you want to find the product of every
*integer except the integer at that index
*
*Bruteforce Approach:
*0(n^2) go through every index and multiply with every nested_index except when index = nested_index
* [Better] Greedy Approach:
* 0(n) time and space: go through greedly twice
* once to multiply before index integers and second for after index integers
*/
public static ArrayList<Integer> getProductsOfInts(ArrayList<Integer>() int_arraylist) {
int sizeOfList = int_arrayList.size();
//make an arrayList to hold our products
ArrayList <Integer> product_of_ints = new ArrayList<Integer> (Collections.copy(sizeOfList, 1);
// for each int, find the product so far for every integer before it and store the product
int product = 1, i= 0;
while(i < sizeOfList){
products_of_ints.add(i, product);
product *= int_arrayList.get(i);
i++;
}
// Then, for each int find the product so far for every integer after it and store that product
//reset product
product = 1;
i = sizeOfList - 1;
while( i >= 0){
products_of_ints *= product;
product *= int_arrayList.get(i);
i--;
}
return products_of_ints;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment