Product of everything except current

Product of everything except current
Write a function that takes as input two integer arrays of length len, input and index, and generates a third array, result, such that:
result[i] = product of everything in input except input[index[i]]
Specifically:
void everythingExcept(int len,                // in parameters
                      int *input, int *index,
                      int *result             // out parameter
                     );
For instance, if the function is called with len=4, input={2,3,4,5}, and index={1,3,2,0}, then result will be set to {40,24,30,60}.
IMPORTANT: Your algorithm must run in linear time.
If you would like to implement the solution in C#, consider the following signature:
public int[] everythingExcept(int[] input, int[] index);

Answer:
For example, if we have 4 elements in input array, we could calculate product like this:
Step1         a1 a2 a3 a4
                 1  *   *  *
                 *  *   *  1
—————————
Step 2     a1   a2  a3 a4
              1    *   *   *
              1*a1 *   *   *
              *    *   *   a4*1
              *    *   *   1
——————————
Step 3     a1    a2  a3 a4
              1     *   *   *
              a1    *   a3*a4
              a1*a2    *   a4
              *     *   *   1
——————————
Step 4   a1    a2  a3 a4
           1     a2*a3*a4
           a1    *   a3*a4
           a1*a2    *   a4
           a1*a2*a3     1

code written in notepad:
public int[] everythingExcept(int[] input, int[] index)
{
    // null, empty, index range check
    int[,] pairs = new int[input.Length,2];
    pairs[0,0] = 1;
    for(int i = 1; i< input.Length ; i++)
    {
        pairs[i,0] = pairs[i-1,0] * input[i-1];
    }
    pairs[input.Length-1,1] = 1;
    for(int i = input.Length – 2; i>=0; i–)
    {
        pairs[i,1] = pairs[i+1,1] * input[i+1];
    }
    int[] result = new result[input.Length];
    for(int i = 0; i < result.Length; i++)
    {
        reuslt[i] = pairs[index[i],0] * pairs[index[i],1];
    }
    return result;
}
NOTE: we can’t calculate product of all elements then divide each element, because product of all elements might be great than Int32.MaxValue but result array don’t.

Advertisements
This entry was posted in 计算机与 Internet. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s