Skip to content

Instantly share code, notes, and snippets.

@Flappizy
Created May 2, 2021 02:54
Show Gist options
  • Save Flappizy/8412e39b804e38951973465cbadd5e41 to your computer and use it in GitHub Desktop.
Save Flappizy/8412e39b804e38951973465cbadd5e41 to your computer and use it in GitHub Desktop.
Find Products of each index in array excluding the index
class ElementProducts
{
//This algorithm works in a way that, i try to find the products of a given array from the left edge up to index i example {1, arr[0], arr[0]*arr[1],
//arr[1]*arr[2]*arr[3] }
//Then i try to find the products of the given array from the right edge up to index i example {arr[1]*arr[2]*arr[3], arr[2]*arr[3], arr[3], 1}
//Then i take the two resulting edges left and right and multiply their element at corresponding position against each other example "products[] =
//left[0] * right[0]" and it goes on like that until i reach the final index
public static int[] FindElementProduct(int[] array)
{
if (array?.Length == null)
{
throw new InvalidOperationException("Array is empty");
}
int[] products = new int[array.Length];
int product = 1;
for (int i = 0; i < array.Length; i++)
{
products[i] = product;
product *= array[i];
}
product = 1;
//The trick here is that i was trying to avoid a space complexity of O(N) so instead of creating two new arrays for the products of the right
//edge to index i and the final resulting products
//i used the product variable to temporarily hold the product of each index from the right edge and immediately
//multiplied it against what i already have in the products variale(left edge results). Hope it makes sense
for (int i = array.Length -1; i >= 0; i--)
{
products[i] *= product;
product *= array[i];
}
return products;
}
static void Main(string[] args)
{
int[] array = { 4, 5, 10, 2 };
int[] products = ElementProducts.FindElementProduct(array);
foreach (var item in products)
{
Console.Write(item + " ");
}
}
}
@meekg33k
Copy link

meekg33k commented May 4, 2021

Hello @Flappizzy, congratulations, you are one of the winners of the $20 award 🎉🎉for Week 4 of #AlgorithmFridays.

Your solution was selected because it is optimal, well-explained through use of good commenting and also handles the edge case for when one of the numbers in the array is 0. Awesome stuff!

We will contact you between 24 - 48 for your award.

Congratulations once again and thanks for participating!

@Flappizy
Copy link
Author

Flappizy commented May 6, 2021

Alright thank you :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment