Given an array of numbers, return array of products of all other numbers (no division)
ArraysAlgorithmArrays Problem Overview
I was asked this question in a job interview, and I'd like to know how others would solve it. I'm most comfortable with Java, but solutions in other languages are welcome.
> Given an array of numbers, nums, return an array of numbers products, where products[i] is the product of all nums[j], j != i.
>
> Input : [1, 2, 3, 4, 5]
> Output: [(2345), (1345), (1245), (1235), (123*4)]
> = [120, 60, 40, 30, 24]
>
> You must do this in O(N) without using division.
Arrays Solutions
Solution 1 - Arrays
An explanation of polygenelubricants method is:
The trick is to construct the arrays (in the case for 4 elements):
{ 1, a[0], a[0]*a[1], a[0]*a[1]*a[2], }
{ a[1]*a[2]*a[3], a[2]*a[3], a[3], 1, }
Both of which can be done in O(n) by starting at the left and right edges respectively.
Then, multiplying the two arrays element-by-element gives the required result.
My code would look something like this:
int a[N] // This is the input
int products_below[N];
int p = 1;
for (int i = 0; i < N; ++i) {
products_below[i] = p;
p *= a[i];
}
int products_above[N];
p = 1;
for (int i = N - 1; i >= 0; --i) {
products_above[i] = p;
p *= a[i];
}
int products[N]; // This is the result
for (int i = 0; i < N; ++i) {
products[i] = products_below[i] * products_above[i];
}
If you need the solution be O(1) in space as well, you can do this (which is less clear in my opinion):
int a[N] // This is the input
int products[N];
// Get the products below the current index
int p = 1;
for (int i = 0; i < N; ++i) {
products[i] = p;
p *= a[i];
}
// Get the products above the current index
p = 1;
for (int i = N - 1; i >= 0; --i) {
products[i] *= p;
p *= a[i];
}
Solution 2 - Arrays
Here is a small recursive function (in C++) to do the modification in-place. It requires O(n) extra space (on stack) though. Assuming the array is in a and N holds the array length, we have:
int multiply(int *a, int fwdProduct, int indx) {
int revProduct = 1;
if (indx < N) {
revProduct = multiply(a, fwdProduct*a[indx], indx+1);
int cur = a[indx];
a[indx] = fwdProduct * revProduct;
revProduct *= cur;
}
return revProduct;
}
Solution 3 - Arrays
Here's my attempt to solve it in Java. Apologies for the non-standard formatting, but the code has a lot of duplication, and this is the best I can do to make it readable.
import java.util.Arrays;
public class Products {
static int[] products(int... nums) {
final int N = nums.length;
int[] prods = new int[N];
Arrays.fill(prods, 1);
for (int
i = 0, pi = 1 , j = N-1, pj = 1 ;
(i < N) && (j >= 0) ;
pi *= nums[i++] , pj *= nums[j--] )
{
prods[i] *= pi ; prods[j] *= pj ;
}
return prods;
}
public static void main(String[] args) {
System.out.println(
Arrays.toString(products(1, 2, 3, 4, 5))
); // prints "[120, 60, 40, 30, 24]"
}
}
The loop invariants are pi = nums[0] * nums[1] *.. nums[i-1] and pj = nums[N-1] * nums[N-2] *.. nums[j+1]. The i part on the left is the "prefix" logic, and the j part on the right is the "suffix" logic.
Recursive one-liner
Jasmeet gave a (beautiful!) recursive solution; I've turned it into this (hideous!) Java one-liner. It does in-place modification, with O(N) temporary space in the stack.
static int multiply(int[] nums, int p, int n) {
return (n == nums.length) ? 1
: nums[n] * (p = multiply(nums, nums[n] * (nums[n] = p), n + 1))
+ 0*(nums[n] *= p);
}
int[] arr = {1,2,3,4,5};
multiply(arr, 1, 0);
System.out.println(Arrays.toString(arr));
// prints "[120, 60, 40, 30, 24]"
Solution 4 - Arrays
Translating Michael Anderson's solution into Haskell:
otherProducts xs = zipWith (*) below above
where below = scanl (*) 1 $ init xs
above = tail $ scanr (*) 1 xs
Solution 5 - Arrays
Sneakily circumventing the "no divisions" rule:
sum = 0.0
for i in range(a):
sum += log(a[i])
for i in range(a):
output[i] = exp(sum - log(a[i]))
Solution 6 - Arrays
Here you go, simple and clean solution with O(N) complexity:
int[] a = {1,2,3,4,5};
int[] r = new int[a.length];
int x = 1;
r[0] = 1;
for (int i=1;i<a.length;i++){
r[i]=r[i-1]*a[i-1];
}
for (int i=a.length-1;i>0;i--){
x=x*a[i];
r[i-1]=x*r[i-1];
}
for (int i=0;i<r.length;i++){
System.out.println(r[i]);
}
Solution 7 - Arrays
- Travel Left->Right and keep saving product. Call it Past. -> O(n)
- Travel Right -> left keep the product. Call it Future. -> O(n)
- Result[i] = Past[i-1] * future[i+1] -> O(n)
- Past[-1] = 1; and Future[n+1]=1;
O(n)
Solution 8 - Arrays
C++, O(n):
long long prod = accumulate(in.begin(), in.end(), 1LL, multiplies<int>());
transform(in.begin(), in.end(), back_inserter(res),
bind1st(divides<long long>(), prod));
Solution 9 - Arrays
Here is my solution in modern C++. It makes use of std::transform and is pretty easy to remember.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
vector<int>& multiply_up(vector<int>& v){
v.insert(v.begin(),1);
transform(v.begin()+1, v.end()
,v.begin()
,v.begin()+1
,[](auto const& a, auto const& b) { return b*a; }
);
v.pop_back();
return v;
}
int main() {
vector<int> v = {1,2,3,4,5};
auto vr = v;
reverse(vr.begin(),vr.end());
multiply_up(v);
multiply_up(vr);
reverse(vr.begin(),vr.end());
transform(v.begin(),v.end()
,vr.begin()
,v.begin()
,[](auto const& a, auto const& b) { return b*a; }
);
for(auto& i: v) cout << i << " ";
}
Solution 10 - Arrays
Precalculate the product of the numbers to the left and to the right of each element. For every element the desired value is the product of it's neigbors's products.
#include <stdio.h>
unsigned array[5] = { 1,2,3,4,5};
int main(void)
{
unsigned idx;
unsigned left[5]
, right[5];
left[0] = 1;
right[4] = 1;
/* calculate products of numbers to the left of [idx] */
for (idx=1; idx < 5; idx++) {
left[idx] = left[idx-1] * array[idx-1];
}
/* calculate products of numbers to the right of [idx] */
for (idx=4; idx-- > 0; ) {
right[idx] = right[idx+1] * array[idx+1];
}
for (idx=0; idx <5 ; idx++) {
printf("[%u] Product(%u*%u) = %u\n"
, idx, left[idx] , right[idx] , left[idx] * right[idx] );
}
return 0;
}
Result:
$ ./a.out
[0] Product(1*120) = 120
[1] Product(1*60) = 60
[2] Product(2*20) = 40
[3] Product(6*5) = 30
[4] Product(24*1) = 24
(UPDATE: now I look closer, this uses the same method as Michael Anderson, Daniel Migowski and polygenelubricants above)
Solution 11 - Arrays
Tricky:
Use the following:
public int[] calc(int[] params) {
int[] left = new int[n-1]
in[] right = new int[n-1]
int fac1 = 1;
int fac2 = 1;
for( int i=0; i<n; i++ ) {
fac1 = fac1 * params[i];
fac2 = fac2 * params[n-i];
left[i] = fac1;
right[i] = fac2;
}
fac = 1;
int[] results = new int[n];
for( int i=0; i<n; i++ ) {
results[i] = left[i] * right[i];
}
Yes, I am sure i missed some i-1 instead of i, but thats the way to solve it.
Solution 12 - Arrays
This is O(n^2) but f# is soooo beautiful:
List.fold (fun seed i -> List.mapi (fun j x -> if i=j+1 then x else x*i) seed)
[1;1;1;1;1]
[1..5]
Solution 13 - Arrays
There also is a O(N^(3/2)) non-optimal solution. It is quite interesting, though.
First preprocess each partial multiplications of size N^0.5(this is done in O(N) time complexity). Then, calculation for each number's other-values'-multiple can be done in 2*O(N^0.5) time(why? because you only need to multiple the last elements of other ((N^0.5) - 1) numbers, and multiply the result with ((N^0.5) - 1) numbers that belong to the group of the current number). Doing this for each number, one can get O(N^(3/2)) time.
Example:
4 6 7 2 3 1 9 5 8
partial results: 467 = 168 231 = 6 958 = 360
To calculate the value of 3, one needs to multiply the other groups' values 168360, and then with 21.
Solution 14 - Arrays
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 4, 5 };
int[] result = { 1, 1, 1, 1, 1 };
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
result[i] *= arr[j];
}
for (int k = arr.length - 1; k > i; k--) {
result[i] *= arr[k];
}
}
for (int i : result) {
System.out.println(i);
}
}
This solution i came up with and i found it so clear what do you think!?
Solution 15 - Arrays
def productify(arr, prod, i):
if i < len(arr):
prod.append(arr[i - 1] * prod[i - 1]) if i > 0 else prod.append(1)
retval = productify(arr, prod, i + 1)
prod[i] *= retval
return retval * arr[i]
return 1
if __name__ == "__main__":
arr = [1, 2, 3, 4, 5]
prod = []
productify(arr, prod, 0)
print(prod)
Solution 16 - Arrays
Based on Billz answer--sorry I can't comment, but here is a scala version that correctly handles duplicate items in the list, and is probably O(n):
val list1 = List(1, 7, 3, 3, 4, 4)
val view = list1.view.zipWithIndex map { x => list1.view.patch(x._2, Nil, 1).reduceLeft(_*_)}
view.force
returns:
List(1008, 144, 336, 336, 252, 252)
Solution 17 - Arrays
Adding my javascript solution here as I didn't find anyone suggesting this. What is to divide, except to count the number of times you can extract a number from another number? I went through calculating the product of the whole array, and then iterate over each element, and substracting the current element until zero:
//No division operation allowed
// keep substracting divisor from dividend, until dividend is zero or less than divisor
function calculateProducsExceptCurrent_NoDivision(input){
var res = [];
var totalProduct = 1;
//calculate the total product
for(var i = 0; i < input.length; i++){
totalProduct = totalProduct * input[i];
}
//populate the result array by "dividing" each value
for(var i = 0; i < input.length; i++){
var timesSubstracted = 0;
var divisor = input[i];
var dividend = totalProduct;
while(divisor <= dividend){
dividend = dividend - divisor;
timesSubstracted++;
}
res.push(timesSubstracted);
}
return res;
}
Solution 18 - Arrays
Well,this solution can be considered that of C/C++. Lets say we have an array "a" containing n elements like a[n],then the pseudo code would be as below.
for(j=0;j<n;j++)
{
prod[j]=1;
for (i=0;i<n;i++)
{
if(i==j)
continue;
else
prod[j]=prod[j]*a[i];
}
Solution 19 - Arrays
One more solution, Using division. with twice traversal. Multiply all the elements and then start dividing it by each element.
Solution 20 - Arrays
{-
Recursive solution using sqrt(n) subsets. Runs in O(n).
Recursively computes the solution on sqrt(n) subsets of size sqrt(n).
Then recurses on the product sum of each subset.
Then for each element in each subset, it computes the product with
the product sum of all other products.
Then flattens all subsets.
Recurrence on the run time is T(n) = sqrt(n)*T(sqrt(n)) + T(sqrt(n)) + n
Suppose that T(n) ≤ cn in O(n).
T(n) = sqrt(n)T(sqrt(n)) + T(sqrt(n)) + n
≤ sqrt(n)csqrt(n) + csqrt(n) + n
≤ cn + csqrt(n) + n
≤ (2c+1)*n
∈ O(n)
Note that ceiling(sqrt(n)) can be computed using a binary search
and O(logn) iterations, if the sqrt instruction is not permitted.
-}
otherProducts [] = []
otherProducts [x] = [1]
otherProducts [x,y] = [y,x]
otherProducts a = foldl' (++) [] $ zipWith (\s p -> map (*p) s) solvedSubsets subsetOtherProducts
where
n = length a
-- Subset size. Require that 1 < s < n.
s = ceiling $ sqrt $ fromIntegral n
solvedSubsets = map otherProducts subsets
subsetOtherProducts = otherProducts $ map product subsets
subsets = reverse $ loop a []
where loop [] acc = acc
loop a acc = loop (drop s a) ((take s a):acc)
Solution 21 - Arrays
Here is my code:
int multiply(int a[],int n,int nextproduct,int i)
{
int prevproduct=1;
if(i>=n)
return prevproduct;
prevproduct=multiply(a,n,nextproduct*a[i],i+1);
printf(" i=%d > %d\n",i,prevproduct*nextproduct);
return prevproduct*a[i];
}
int main()
{
int a[]={2,4,1,3,5};
multiply(a,5,1,0);
return 0;
}
Solution 22 - Arrays
Here's a slightly functional example, using C#:
Func<long>[] backwards = new Func<long>[input.Length];
Func<long>[] forwards = new Func<long>[input.Length];
for (int i = 0; i < input.Length; ++i)
{
var localIndex = i;
backwards[i] = () => (localIndex > 0 ? backwards[localIndex - 1]() : 1) * input[localIndex];
forwards[i] = () => (localIndex < input.Length - 1 ? forwards[localIndex + 1]() : 1) * input[localIndex];
}
var output = new long[input.Length];
for (int i = 0; i < input.Length; ++i)
{
if (0 == i)
{
output[i] = forwards[i + 1]();
}
else if (input.Length - 1 == i)
{
output[i] = backwards[i - 1]();
}
else
{
output[i] = forwards[i + 1]() * backwards[i - 1]();
}
}
I'm not entirely certain that this is O(n), due to the semi-recursion of the created Funcs, but my tests seem to indicate that it's O(n) in time.
Solution 23 - Arrays
To be complete here is the code in Scala:
val list1 = List(1, 2, 3, 4, 5)
for (elem <- list1) println(list1.filter(_ != elem) reduceLeft(_*_))
This will print out the following:
120
60
40
30
24
The program will filter out the current elem (_ != elem); and multiply the new list with reduceLeft method. I think this will be O(n) if you use scala view or Iterator for lazy eval.
Solution 24 - Arrays
// This is the recursive solution in Java // Called as following from main product(a,1,0);
public static double product(double[] a, double fwdprod, int index){
double revprod = 1;
if (index < a.length){
revprod = product2(a, fwdprod*a[index], index+1);
double cur = a[index];
a[index] = fwdprod * revprod;
revprod *= cur;
}
return revprod;
}
Solution 25 - Arrays
A neat solution with O(n) runtime:
-
For each element calculate the product of all the elements that occur before that and it store in an array "pre".
-
For each element calculate the product of all the elements that occur after that element and store it in an array "post"
-
Create a final array "result", for an element i,
result[i] = pre[i-1]*post[i+1];
Solution 26 - Arrays
Here is another simple concept which solves the problem in O(N).
int[] arr = new int[] {1, 2, 3, 4, 5};
int[] outArray = new int[arr.length];
for(int i=0;i<arr.length;i++){
int res=Arrays.stream(arr).reduce(1, (a, b) -> a * b);
outArray[i] = res/arr[i];
}
System.out.println(Arrays.toString(outArray));
Solution 27 - Arrays
We can exclude the nums[j] (where j != i) from list first, then get the product of the rest; The following is a python way to solve this puzzle:
from functools import reduce
def products(nums):
return [ reduce(lambda x,y: x * y, nums[:i] + nums[i+1:]) for i in range(len(nums)) ]
print(products([1, 2, 3, 4, 5]))
[out]
[120, 60, 40, 30, 24]
Solution 28 - Arrays
Here is the ptyhon version
# This solution use O(n) time and O(n) space
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
N = len(nums)
if N == 0: return
# Initialzie list of 1, size N
l_prods, r_prods = [1]*N, [1]*N
for i in range(1, N):
l_prods[i] = l_prods[i-1] * nums[i-1]
for i in reversed(range(N-1)):
r_prods[i] = r_prods[i+1] * nums[i+1]
result = [x*y for x,y in zip(l_prods,r_prods)]
return result
# This solution use O(n) time and O(1) space
def productExceptSelfSpaceOptimized(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
N = len(nums)
if N == 0: return
# Initialzie list of 1, size N
result = [1]*N
for i in range(1, N):
result[i] = result[i-1] * nums[i-1]
r_prod = 1
for i in reversed(range(N)):
result[i] *= r_prod
r_prod *= nums[i]
return result
Solution 29 - Arrays
I'm use to C#:
public int[] ProductExceptSelf(int[] nums)
{
int[] returnArray = new int[nums.Length];
List<int> auxList = new List<int>();
int multTotal = 0;
// If no zeros are contained in the array you only have to calculate it once
if(!nums.Contains(0))
{
multTotal = nums.ToList().Aggregate((a, b) => a * b);
for (int i = 0; i < nums.Length; i++)
{
returnArray[i] = multTotal / nums[i];
}
}
else
{
for (int i = 0; i < nums.Length; i++)
{
auxList = nums.ToList();
auxList.RemoveAt(i);
if (!auxList.Contains(0))
{
returnArray[i] = auxList.Aggregate((a, b) => a * b);
}
else
{
returnArray[i] = 0;
}
}
}
return returnArray;
}
Solution 30 - Arrays
Here is simple Scala version in Linear O(n) time:
def getProductEff(in:Seq[Int]):Seq[Int] = {
//create a list which has product of every element to the left of this element
val fromLeft = in.foldLeft((1, Seq.empty[Int]))((ac, i) => (i * ac._1, ac._2 :+ ac._1))._2
//create a list which has product of every element to the right of this element, which is the same as the previous step but in reverse
val fromRight = in.reverse.foldLeft((1,Seq.empty[Int]))((ac,i) => (i * ac._1,ac._2 :+ ac._1))._2.reverse
//merge the two list by product at index
in.indices.map(i => fromLeft(i) * fromRight(i))
}
This works because essentially the answer is an array which has product of all elements to the left and to the right.
Solution 31 - Arrays
import java.util.Arrays;
public class Pratik
{
public static void main(String[] args)
{
int[] array = {2, 3, 4, 5, 6}; // OUTPUT: 360 240 180 144 120
int[] products = new int[array.length];
arrayProduct(array, products);
System.out.println(Arrays.toString(products));
}
public static void arrayProduct(int array[], int products[])
{
double sum = 0, EPSILON = 1e-9;
for(int i = 0; i < array.length; i++)
sum += Math.log(array[i]);
for(int i = 0; i < array.length; i++)
products[i] = (int) (EPSILON + Math.exp(sum - Math.log(array[i])));
}
}
OUTPUT:
[360, 240, 180, 144, 120]
> Time complexity : O(n) > > Space complexity: O(1)
Solution 32 - Arrays
My first try, in Python. O(2n):
def product(l):
product = 1
num_zeroes = 0
pos_zero = -1
# Multiply all and set positions
for i, x in enumerate(l):
if x != 0:
product *= x
l[i] = 1.0/x
else:
num_zeroes += 1
pos_zero = i
# Warning! Zeroes ahead!
if num_zeroes > 0:
l = [0] * len(l)
if num_zeroes == 1:
l[pos_zero] = product
else:
# Now set the definitive elements
for i in range(len(l)):
l[i] = int(l[i] * product)
return l
if __name__ == "__main__":
print("[0, 0, 4] = " + str(product([0, 0, 4])))
print("[3, 0, 4] = " + str(product([3, 0, 4])))
print("[1, 2, 3] = " + str(product([1, 2, 3])))
print("[2, 3, 4, 5, 6] = " + str(product([2, 3, 4, 5, 6])))
print("[2, 1, 2, 2, 3] = " + str(product([2, 1, 2, 2, 3])))
Output:
[0, 0, 4] = [0, 0, 0]
[3, 0, 4] = [0, 12, 0]
[1, 2, 3] = [6, 3, 2]
[2, 3, 4, 5, 6] = [360, 240, 180, 144, 120]
[2, 1, 2, 2, 3] = [12, 24, 12, 12, 8]
Solution 33 - Arrays
Here is a C implementation
O(n) time complexity.
INPUT
#include<stdio.h>
int main()
{
int x;
printf("Enter The Size of Array : ");
scanf("%d",&x);
int array[x-1],i ;
printf("Enter The Value of Array : \n");
for( i = 0 ; i <= x-1 ; i++)
{
printf("Array[%d] = ",i);
scanf("%d",&array[i]);
}
int left[x-1] , right[x-1];
left[0] = 1 ;
right[x-1] = 1 ;
for( i = 1 ; i <= x-1 ; i++)
{
left[i] = left[i-1] * array[i-1];
}
printf("\nThis is Multiplication of array[i-1] and left[i-1]\n");
for( i = 0 ; i <= x-1 ; i++)
{
printf("Array[%d] = %d , Left[%d] = %d\n",i,array[i],i,left[i]);
}
for( i = x-2 ; i >= 0 ; i--)
{
right[i] = right[i+1] * array[i+1];
}
printf("\nThis is Multiplication of array[i+1] and right[i+1]\n");
for( i = 0 ; i <= x-1 ; i++)
{
printf("Array[%d] = %d , Right[%d] = %d\n",i,array[i],i,right[i]);
}
printf("\nThis is Multiplication of Right[i] * Left[i]\n");
for( i = 0 ; i <= x-1 ; i++)
{
printf("Right[%d] * left[%d] = %d * %d = %d\n",i,i,right[i],left[i],right[i]*left[i]);
}
return 0 ;
}
OUTPUT
Enter The Size of Array : 5
Enter The Value of Array :
Array[0] = 1
Array[1] = 2
Array[2] = 3
Array[3] = 4
Array[4] = 5
This is Multiplication of array[i-1] and left[i-1]
Array[0] = 1 , Left[0] = 1
Array[1] = 2 , Left[1] = 1
Array[2] = 3 , Left[2] = 2
Array[3] = 4 , Left[3] = 6
Array[4] = 5 , Left[4] = 24
This is Multiplication of array[i+1] and right[i+1]
Array[0] = 1 , Right[0] = 120
Array[1] = 2 , Right[1] = 60
Array[2] = 3 , Right[2] = 20
Array[3] = 4 , Right[3] = 5
Array[4] = 5 , Right[4] = 1
This is Multiplication of Right[i] * Left[i]
Right[0] * left[0] = 120 * 1 = 120
Right[1] * left[1] = 60 * 1 = 60
Right[2] * left[2] = 20 * 2 = 40
Right[3] * left[3] = 5 * 6 = 30
Right[4] * left[4] = 1 * 24 = 24
Process returned 0 (0x0) execution time : 6.548 s
Press any key to continue.
Solution 34 - Arrays
Just 2 passes up and down. Job done in O(N)
private static int[] multiply(int[] numbers) {
int[] multiplied = new int[numbers.length];
int total = 1;
multiplied[0] = 1;
for (int i = 1; i < numbers.length; i++) {
multiplied[i] = numbers[i - 1] * multiplied[i - 1];
}
for (int j = numbers.length - 2; j >= 0; j--) {
total *= numbers[j + 1];
multiplied[j] = total * multiplied[j];
}
return multiplied;
}
Solution 35 - Arrays
def products(nums):
prefix_products = []
for num in nums:
if prefix_products:
prefix_products.append(prefix_products[-1] * num)
else:
prefix_products.append(num)
suffix_products = []
for num in reversed(nums):
if suffix_products:
suffix_products.append(suffix_products[-1] * num)
else:
suffix_products.append(num)
suffix_products = list(reversed(suffix_products))
result = []
for i in range(len(nums)):
if i == 0:
result.append(suffix_products[i + 1])
elif i == len(nums) - 1:
result.append(prefix_products[i-1])
else:
result.append(
prefix_products[i-1] * suffix_products[i+1]
)
return result
Solution 36 - Arrays
We're factoring elements of the array, first from before the index i.e. the prefix then after the index or postfix
class Solution:
def productExceptSelf(nums):
length = len(nums)
result = [1] * length
prefix_product = 1
postfix_product = 1
# we initialize the result and products
for i in range(length)
result[i] *= prefix_product
prefix_product *= nums[i]
#we multiply the result by each number before the index
for i in range(length-1,-1,-1)
result[i] *= postfix_product
postfix_product *= nums[i]
#same for after index
return result
sorry on mobile on my walk
Solution 37 - Arrays
php version
using array_product function without division.
If we set i value to 1 temporary, than array product will do exactly what we need
<?php
function product($key, $arr)
{
$arr[$key] = 1;
return array_product($arr);
};
$arr = [1, 2, 3, 4, 5];
$newarr = array();
foreach ($arr as $key => $value) {
$newarr[$key] = product($key, $arr);
}
print_r($newarr);
Solution 38 - Arrays
Try this!
import java.util.*;
class arrProduct
{
public static void main(String args[])
{
//getting the size of the array
Scanner s = new Scanner(System.in);
int noe = s.nextInt();
int out[]=new int[noe];
int arr[] = new int[noe];
// getting the input array
for(int k=0;k<noe;k++)
{
arr[k]=s.nextInt();
}
int val1 = 1,val2=1;
for(int i=0;i<noe;i++)
{
int res=1;
for(int j=1;j<noe;j++)
{
if((i+j)>(noe-1))
{
int diff = (i+j)-(noe);
if(arr[diff]!=0)
{
res = res * arr[diff];
}
}
else
{
if(arr[i+j]!=0)
{
res= res*arr[i+j];
}
}
out[i]=res;
}
}
//printing result
System.out.print("Array of Product: [");
for(int l=0;l<out.length;l++)
{
if(l!=out.length-1)
{
System.out.print(out[l]+",");
}
else
{
System.out.print(out[l]);
}
}
System.out.print("]");
}
}
Solution 39 - Arrays
Coded up using EcmaScript 2015
'use strict'
/*
Write a function that, given an array of n integers, returns an array of all possible products using exactly (n - 1) of those integers.
*/
/*
Correct behavior:
- the output array will have the same length as the input array, ie. one result array for each skipped element
- to compare result arrays properly, the arrays need to be sorted
- if array lemgth is zero, result is empty array
- if array length is 1, result is a single-element array of 1
input array: [1, 2, 3]
1*2 = 2
1*3 = 3
2*3 = 6
result: [2, 3, 6]
*/
class Test {
setInput(i) {
this.input = i
return this
}
setExpected(e) {
this.expected = e.sort()
return this
}
}
class FunctionTester {
constructor() {
this.tests = [
new Test().setInput([1, 2, 3]).setExpected([6, 3, 2]),
new Test().setInput([2, 3, 4, 5, 6]).setExpected([3 * 4 * 5 * 6, 2 * 4 * 5 * 6, 2 * 3 * 5 * 6, 2 * 3 * 4 * 6, 2 * 3 * 4 * 5]),
]
}
test(f) {
console.log('function:', f.name)
this.tests.forEach((test, index) => {
var heading = 'Test #' + index + ':'
var actual = f(test.input)
var failure = this._check(actual, test)
if (!failure) console.log(heading, 'input:', test.input, 'output:', actual)
else console.error(heading, failure)
return !failure
})
}
testChain(f) {
this.test(f)
return this
}
_check(actual, test) {
if (!Array.isArray(actual)) return 'BAD: actual not array'
if (actual.length !== test.expected.length) return 'BAD: actual length is ' + actual.length + ' expected: ' + test.expected.length
if (!actual.every(this._isNumber)) return 'BAD: some actual values are not of type number'
if (!actual.sort().every(isSame)) return 'BAD: arrays not the same: [' + actual.join(', ') + '] and [' + test.expected.join(', ') + ']'
function isSame(value, index) {
return value === test.expected[index]
}
}
_isNumber(v) {
return typeof v === 'number'
}
}
/*
Efficient: use two iterations of an aggregate product
We need two iterations, because one aggregate goes from last-to-first
The first iteration populates the array with products of indices higher than the skipped index
The second iteration calculates products of indices lower than the skipped index and multiplies the two aggregates
input array:
1 2 3
2*3
1* 3
1*2
input array:
2 3 4 5 6
(3 * 4 * 5 * 6)
(2) * 4 * 5 * 6
(2 * 3) * 5 * 6
(2 * 3 * 4) * (6)
(2 * 3 * 4 * 5)
big O: (n - 2) + (n - 2)+ (n - 2) = 3n - 6 => o(3n)
*/
function multiplier2(ns) {
var result = []
if (ns.length > 1) {
var lastIndex = ns.length - 1
var aggregate
// for the first iteration, there is nothing to do for the last element
var index = lastIndex
for (var i = 0; i < lastIndex; i++) {
if (!i) aggregate = ns[index]
else aggregate *= ns[index]
result[--index] = aggregate
}
// for second iteration, there is nothing to do for element 0
// aggregate does not require multiplication for element 1
// no multiplication is required for the last element
for (var i = 1; i <= lastIndex; i++) {
if (i === 1) aggregate = ns[0]
else aggregate *= ns[i - 1]
if (i !== lastIndex) result[i] *= aggregate
else result[i] = aggregate
}
} else if (ns.length === 1) result[0] = 1
return result
}
/*
Create the list of products by iterating over the input array
the for loop is iterated once for each input element: that is n
for every n, we make (n - 1) multiplications, that becomes n (n-1)
O(n^2)
*/
function multiplier(ns) {
var result = []
for (var i = 0; i < ns.length; i++) {
result.push(ns.reduce((reduce, value, index) =>
!i && index === 1 ? value // edge case: we should skip element 0 and it's the first invocation: ignore reduce
: index !== i ? reduce * value // multiply if it is not the element that should be skipped
: reduce))
}
return result
}
/*
Multiply by clone the array and remove one of the integers
O(n^2) and expensive array manipulation
*/
function multiplier0(ns) {
var result = []
for (var i = 0; i < ns.length; i++) {
var ns1 = ns.slice() // clone ns array
ns1.splice(i, 1) // remove element i
result.push(ns1.reduce((reduce, value) => reduce * value))
}
return result
}
new FunctionTester().testChain(multiplier0).testChain(multiplier).testChain(multiplier2)
run with Node.js v4.4.5 like:
> node --harmony integerarrays.js
function: multiplier0
Test #0: input: [ 1, 2, 3 ] output: [ 2, 3, 6 ]
Test #1: input: [ 2, 3, 4, 5, 6 ] output: [ 120, 144, 180, 240, 360 ]
function: multiplier
Test #0: input: [ 1, 2, 3 ] output: [ 2, 3, 6 ]
Test #1: input: [ 2, 3, 4, 5, 6 ] output: [ 120, 144, 180, 240, 360 ]
function: multiplier2
Test #0: input: [ 1, 2, 3 ] output: [ 2, 3, 6 ]
Test #1: input: [ 2, 3, 4, 5, 6 ] output: [ 120, 144, 180, 240, 360 ]
Solution 40 - Arrays
I have a solution with O(n) space and O(n^2) time complexity provided below,
public static int[] findEachElementAsProduct1(final int[] arr) {
int len = arr.length;
// int[] product = new int[len];
// Arrays.fill(product, 1);
int[] product = IntStream.generate(() -> 1).limit(len).toArray();
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
if (i == j) {
continue;
}
product[i] *= arr[j];
}
}
return product;
}
Solution 41 - Arrays
I got asked this question recently, and whilst I couldn't get O(N) during it, I had a different approach (unfortunately O(N^2)) but thought I'd share anyway.
Convert to List<Integer> first.
Loop through original array array.length() times.
Use a while loop to multiple the next set of required numbers:
while (temp < list.size() - 1) {
res *= list.get(temp);
temp++;
}
Then add res to a new array (which of course you've declared earlier), then add the value at array[i] to the List, and continue so forth.
I know this won't be of great use, but it's what I came up with under the pressures of an interview :)
int[] array = new int[]{1, 2, 3, 4, 5};
List<Integer> list = Arrays.stream(array).boxed().collect(Collectors.toList());
int[] newarray = new int[array.length];
int res = 1;
for (int i = 0; i < array.length; i++) {
int temp = i;
while (temp < list.size() - 1) {
res *= list.get(temp);
temp++;
}
newarray[i] = res;
list.add(array[i]);
res = 1;
}
> Output: [24, 120, 60, 40, 30]
Solution 42 - Arrays
Here's a one-liner solution in Ruby.
nums.map { |n| (num - [n]).inject(:*) }
Solution 43 - Arrays
Here is my concise solution using python.
from functools import reduce
def excludeProductList(nums_):
after = [reduce(lambda x, y: x*y, nums_[i:]) for i in range(1, len(nums_))] + [1]
before = [1] + [reduce(lambda x, y: x*y, nums_[:i]) for i in range(1, len(nums_))]
zippedList = list(zip(before, after))
finalList = list(map(lambda x: x[0]*x[1], zippedList))
return finalList
Solution 44 - Arrays
ruby solution
a = [1,2,3,4]
result = []
a.each {|x| result.push( (a-[x]).reject(&:zero?).reduce(:*)) }
puts result
Solution 45 - Arrays
int[] b = new int[] { 1, 2, 3, 4, 5 };
int j;
for(int i=0;i<b.Length;i++)
{
int prod = 1;
int s = b[i];
for(j=i;j<b.Length-1;j++)
{
prod = prod * b[j + 1];
}
int pos = i;
while(pos!=-1)
{
pos--;
if(pos!=-1)
prod = prod * b[pos];
}
Console.WriteLine("\n Output is {0}",prod);
}
Solution 46 - Arrays
A variation in JavaScript using reduce
const getProduct = arr => arr.reduce((acc, value) => acc * value);
const arrayWithExclusion = (arr, node) =>
arr.reduce((acc, val, j) => (node !== j ? [...acc, val] : acc), []);
const getProductWithExclusion = arr => {
let result = [];
for (let i = 0; i < arr.length; i += 1) {
result.push(getProduct(arrayWithExclusion(arr, i)));
}
return result;
};
Solution 47 - Arrays
I came up with 2 solutions in Javascript, one with division and one without
// without division function methodOne(arr) { return arr.map(item => { return arr.reduce((result, num) => { if (num !== item) { result = result * num; } return result; },1) }); }
// with division
function methodTwo(arr) {
var mul = arr.reduce((result, num) => {
result = result * num;
return result;
},1)
return arr.map(item => mul/item);
}
console.log(methodOne([1, 2, 3, 4, 5]));
console.log(methodTwo([1, 2, 3, 4, 5]));
Solution 48 - Arrays
int[] arr1 = { 1, 2, 3, 4, 5 };
int[] product = new int[arr1.Length];
for (int i = 0; i < arr1.Length; i++)
{
for (int j = 0; j < product.Length; j++)
{
if (i != j)
{
product[j] = product[j] == 0 ? arr1[i] : product[j] * arr1[i];
}
}
}