Created
July 21, 2015 23:54
-
-
Save mugizico/a6a87cc7faa2ed9ffdd7 to your computer and use it in GitHub Desktop.
Interview Cake #2 : Products of all integers at that index
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
*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