Created
October 30, 2017 06:31
-
-
Save jianminchen/0d5a4df2c7301957386821329501193d to your computer and use it in GitHub Desktop.
Array of Array products - 40 minutes practice - pass all test cases - first writing with a bug on line 26 ( return array with 0 value for all elements)
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
using System; | |
class Solution | |
{ | |
public static int[] ArrayOfArrayProducts(int[] arr) // 8, 10, 2 | |
{ | |
// your code goes here | |
if(arr == null || arr.Length == 0 || arr.Length == 1) | |
{ | |
return new int[0]; | |
} | |
// assume that array is not empty | |
var length = arr.Length; // 3 | |
var products = new int[length]; // 3 | |
var production = 1; // production | |
// iterate from left to right | |
for(int i = 0; i < length; i++) // 8, 10, 2, visit index = 1, 10, 2 | |
{ | |
var previous = i - 1; | |
var visit = i > 0 ? arr[previous] : 1; // 1, 8, 10 | |
production *= visit; | |
products[i] = production ; // products[0] = 1, 1 * 8, 8 * 10 -> new int[]{1, 8, 80} | |
} | |
// right side -> right -> left | |
production = 1; | |
for(int i = length - 1 ; i >= 0; i-- ) // 2, 10, 8 new int[]{1, 8, 80} -> new int[]{1 * 10 *2, 8 * 2, 80 * 1} | |
{ | |
var previous = i + 1; | |
var visit = i < length - 1 ? arr[previous] : 1; // 1, 2, 10 | |
production *= visit; | |
products[i] *= production ; | |
} | |
return products; | |
} | |
static void Main(string[] args) | |
{ | |
var test1 = ArrayOfArrayProducts(new int[]{8,10,2}) ; | |
foreach(var item in test1) | |
{ | |
Console.WriteLine(item); | |
} | |
} | |
} | |
// input: arr = [8, 10, 2] | |
// output: [20, 16, 80] # by calculating: [10*2, 8*2, 8*10] | |
// input: arr = [2, 7, 3, 4] | |
// output: [84, 24, 56, 42] # by calculating: [7*3*4, 2*3*4, 2*7*4, 2*7*3] | |
// [time limit] 5000ms | |
// 0 ≤ arr.length ≤ 20 | |
// [8, 10, 2] | |
// 10 * 2 -> i, arr[0] * arr[1] * .. arr[i - 1] (called part A) arr[i+1]*arr[i+2]....*arr[n-1] (part B) | |
// dynamic programmer -> two iteration left -> right (part A) | |
// iteration right -> left (part B | |
// multiplcation in total -> redundant -> arr[0] * arr[1] -> multiplication -> *arr[2] -> O(n) + O(n) | |
// left -> right | |
// product = 1 | |
// i = 0 -> i = 1 product *= arr[i -1] -> i=2 , product *= arr[i-1] ... | |
// right -> left |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment