/ Coding

The Unconventional Guide to A Product Array Puzzle

Problem Statement

This problem was asked by Uber.

Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.

For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].

Follow-up: what if you can't use division?

Solution: Brute force Strategy

Refer the code on the link http://rextester.com/XJDMV96017

//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
    public class Program
    {
        public static void Main(string[] args)
        {
            /*
            This problem was asked by Uber.
            Given an array of integers, return a new array such that each element at index i of the new array is 
            the product of all the numbers in the original array except the one at i.
            For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. 
            If our input was [3, 2, 1], the expected output would be [2, 3, 6].
            Follow-up: what if you can't use division?
            */
            var input = new []{1, 2, 3, 4, 5};
            var output = new int[5];
            
            // O(n^2) Approach
            for(int i = 0; i < output.Length; i++){
                output[i] = 1;
                for(int j = 0; j < input.Length; j++){
                    if(j == i){
                        continue;
                    }
                    output[i] *= input[j]; 
                }
            }
            
            Console.WriteLine(string.Join(", ", output));
        }
    }
}

Solution: Using Array Multiplication Results

Array 1 2 3 4 5
Multiplication with Previous 1 (1)*2 (1*2)*3 (123)*4 (123*4)*5
Result 1 2 6 24 120
Reverse Array 5 4 3 2 1
Multiplication with Previous 5 (5)*4 (5*4)*3 (543)*2 (543*2)*1
Reverse Result 5 20 60 120 120

From the above information, we can calculate Reverse Multiplication for the array and use it with Normal Multiplication to achieve the desired output.
For the above example, we could

Pseudo Code

We first calculate the reverse Matrix multiplication of
[1, 2, 3, 4, 5] as [120, 60, 20, 5, 1]

// Reverse Matrix Multiplication
temp = 1
Loop from n=4 to n=1
  Output[n]= temp
  Output[n-1]= temp * input[n] = 5
End

Secondly we use the above reverse Matrix calculation with the normal multiplication
[1, 2, 3, 4, 5] as [1, 2, 6, 24, 120]

// Use Reverse Multiplied output with input
temp = 1;
Loop from n=0 to n=4
    Output[n] = temp * output[n];
    temp *= input[n];
End

Refer the code on the link http://rextester.com/KVA90622

//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
    public class Program
    {
        public static void Main(string[] args)
        {
            /*
            This problem was asked by Uber.
            Given an array of integers, return a new array such that each element at index i of the new array is 
            the product of all the numbers in the original array except the one at i.
            For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. 
            If our input was [3, 2, 1], the expected output would be [2, 3, 6].
            Follow-up: what if you can't use division?
            */
            var input = new []{1, 2, 3, 4, 5};
            var output = new int[input.Length];
            
            // Reverse Multiplication - 1, 5, 20, 60, 120
            // Stored as - 120, 60, 20, 5, 1
            var temp = 1;
            for(int i = input.Length - 1; i > 0; i--){
                output[i] = temp;
                temp *= input[i];
                output[i - 1] = temp;
            }
            temp = 1;
            for(int i = 0; i < input.Length; i++){
                output[i] = temp * output[i];
                temp *= input[i];
            }
            
            Console.WriteLine(string.Join(", ", output));
        }
    }
}
The Unconventional Guide to A Product Array Puzzle
Share this

Subscribe to Coding Today

Popular queries