Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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

This comment has been minimized.

Copy link

@meekg33k 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

This comment has been minimized.

Copy link
Owner Author

@Flappizy 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