## Partial Products Of An Array

### October 20, 2017

We have another homework problem today:

Replace each element of an array with the product of every other element of the array, without using the division operator. For instance, given array (5 3 4 2 6 8), the desired output is (1152 1920 1440 2880 960 720).

Your task is to write a program to replace each element of an array with the product of every other element of the array, without performing division. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 13 Responses to “Partial Products Of An Array”

1. chaw said

The algorithm is essentially the same as in the sample solution,
but this implementation exercises a few SRFI 133 procedures on
vectors.

```(import (scheme base)
(scheme write)
(org eip10 srfi 133)) ; local copy of SRFI 133 sample implementation

(define input-101 '#(5 3 4 2 6 8))
(define output-101 '#(1152 1920 1440 2880 960 720))

;; Theta(n) time and space.
(define (other-products vec)
(let ((evec (vector-append '#(1) vec '#(1)))) ; extend vec with 1 at each end
(let ((lr-chain (vector-cumulate * 1 evec))
(rl-chain (vector-reverse-copy
(vector-cumulate * 1 (vector-reverse-copy evec)))))
(vector-unfold (lambda (idx)
(* (vector-ref lr-chain idx)
(vector-ref rl-chain (+ idx 2))))
(vector-length vec)))))

(display (equal? output-101 (other-products input-101)))
(newline)
```
2. Haskell also has `scanr`. Here’s my golfed version:

```module Main where

ppa :: Num a => [a] -> [a]
ppa = zipWith (*) <\$> init . scanl (*) 1 <*> tail . scanr (*) 1

main :: IO ()
main = print . ppa \$ [1 .. 5 :: Int]
```
3. isaac said

a c solution by a noob:

```#include <stdio.h>

int main() {

int input_array[] = {5,3,4,2,6,8};
int last_index = (sizeof(input_array) / sizeof(int)) - 1;
int output_array[last_index + 1];
int products_array[last_index + 2];
products_array[last_index + 1] = 1;
int i;
int products = 1;
for(i = last_index; i > 0; i--) {
products = products * input_array[i];
products_array[i] = products;
}
output_array = products_array;
products = 1;
for(i = 1; i <= last_index; i++) {
products = products * input_array[i - 1];
output_array[i] = products * products_array[i + 1];
}
output_array[last_index] = products;
for(i = 0; i <= last_index; i++) {
printf("%d\t", output_array[i]);
}

return 0;
output_array[last_index] = products;
for(i = 0; i <= last_index; i++) {
printf("%d\t", output_array[i]);
}

return 0;
}
```
4. Globules said

Another Haskell solution that (it turns out) is almost identical to Graham Enos’ version. A minor difference is that I don’t use the init function, since tail will ensure that the second list is one element shorter than the first, so zipwith will never look at the last element of the first list.

```partProd :: Num a => [a] -> [a]
partProd xs = zipWith (*) (scanl (*) 1 xs) (tail \$ scanr (*) 1 xs)

main :: IO ()
main = do
print \$ partProd []
print \$ partProd 
print \$ partProd [5, 3]
print \$ partProd [5, 3, 4, 2, 6, 8]
```
```\$ ./partprod
[]

[3,5]
[1152,1920,1440,2880,960,720]
```
5. Daniel said

Here’s a solution in x86 assembly.

```/* partial_products.s */

.section .text

.globl partial_products
.type partial_products,@function

# void partial_products(int* input, int* output, int n);
partial_products:
pushl %ebp
movl %esp, %ebp

# %ebp offsets
.equ input, 8
.equ output, 12
.equ n, 16

# Save non-volatile registers
pushl %ebx
pushl %edi
pushl %esi

# create stack space for local variables
movl \$4, %eax # 4 bytes per int
imull n(%ebp), %eax # n elements per array
imull \$2, %eax # 2 local arrays
subl %eax, %esp
# Save the amount of stack space
pushl %eax

movl input(%ebp), %eax # start of input array

# Calculate cumulative products, while iterating forward
movl %esp, %ebx # start of forward array
addl \$4, %ebx # (one element into the stack)
movl \$0, %ecx # array index
movl \$1, %edx # cumulative product
loop1:
cmpl %ecx, n(%ebp)
je loop1_end
movl (%eax, %ecx, 4), %edi # array value
imull %edi, %edx
movl %edx, (%ebx, %ecx, 4)
incl %ecx
jmp loop1
loop1_end:

# Calculate cumulative products, while iterating backward
# Shift %ebx pointer to start of backward array
# (past the end of the forward array)
movl \$4, %ecx # 4 bytes per int
imull n(%ebp), %ecx # n elements per array
addl %ecx, %ebx # start of backward array

movl n(%ebp), %ecx # array index
movl \$1, %edx # cumulative product
loop2:
decl %ecx
cmpl \$-1, %ecx
je loop2_end
movl (%eax, %ecx, 4), %edi # array value
imull %edi, %edx
movl %edx, (%ebx, %ecx, 4)
jmp loop2
loop2_end:

# Calculate output by multiplying leftmost forward
# array value by the rightmost backward array value.
movl %esp, %eax # start of forward array
addl \$4, %eax # (one element into the stack)
movl \$4, %ebx # 4 bytes per int
imull n(%ebp), %ebx # n elements per array
addl %eax, %ebx # start of backward array
movl \$0, %ecx # array index
loop3:
cmpl %ecx, n(%ebp)
je loop3_end
movl (%ebx, %ecx, 4), %edx

movl \$1, %esi
cmpl \$0, %ecx
je left_end
imull -4(%eax, %ecx, 4), %esi
left_end:
movl n(%ebp), %edi
decl %edi
cmpl %edi, %ecx
je right_end
imull 4(%ebx, %ecx, 4), %esi
right_end:
movl output(%ebp), %edi # start of output array
movl %esi, (%edi, %ecx, 4)
incl %ecx
jmp loop3
loop3_end:

# Ignore local variables
popl %eax

# Restore non-volatile registers
popl %esi
popl %edi
popl %ebx

movl %ebp, %esp
popl %ebp
ret
```

Here’s a C program that calls the function.

```/* main.c */

#include <stdio.h>

void partial_products(int*, int*, int);

void print_array(int* array, int n) {
printf("[");
for (int i = 0; i < n; ++i) {
if (i > 0) printf(", ");
printf("%d", array[i]);
}
printf("]");
}

int main(int argc, char* argv[]) {
int array[] = {5, 3, 4, 2, 6, 8};
int n = sizeof(array) / sizeof(int);

printf("array:\n  ");
print_array(array, n);
printf("\n");

int output[n];
partial_products(array, output, n);
printf("partial_products(array):\n  ");
print_array(output, n);
printf("\n");
}
```

Here’s example usage and output.

```\$ as --32 -o partial_products.o partial_products.s
\$ gcc -m32 -o main partial_products.o main.c
\$ ./main
```

<

pre>
array:
[5, 3, 4, 2, 6, 8]
partial_products(array):
[1152, 1920, 1440, 2880, 960, 720]

<

pre>

6. Daniel said

Here’s the output again, hopefully formatted properly this time:

```array:
[5, 3, 4, 2, 6, 8]
partial_products(array):
[1152, 1920, 1440, 2880, 960, 720]
```
7. V said

In Ruby.

```  def partial_product(array)
array.each_with_index.map do |_, i|
array.rotate(i).drop(1).reduce(&:*)
end
end
```
8. kernelbob said

Python 3, in the REPL.

```~\$ python3
Python 3.5.3 (default, May 31 2017, 00:43:27)
[GCC 4.2.1 Compatible Apple LLVM 7.3.0 (clang-703.0.31)] on darwin
>>> from functools import reduce
>>> a = [5, 3, 4, 2, 6, 8]
>>> run_prod = lambda a: reduce(lambda a, b: a + [b * a[-1]], a, )[:-1]
>>> run_prod(a)
[1, 5, 15, 60, 120, 720]
>>> [a * b for (a, b) in zip(run_prod(a), run_prod(a[::-1])[::-1])]
[1152, 1920, 1440, 2880, 960, 720]
>>>
```
9. mj said

a simple java solution below ..

//package com.mayank.randompractice;
import java.util.*;

public class CodeDay1_IDZ {

``````public static void main(String[] args) {

int a[] = new int [] {5,3,4,2,6,8};
int b[] = new int [a.length];
int x=1;

for(int i=0;i<a.length;i++){
for(int j=0;j<a.length;j++){
if(i!=j){
x = a[j]*x;
}

}
b[i]=x;
x=1;
}

System.out.println(Arrays.toString(b));
}
``````

}

10. bavier said

Simple recursive solution in Guile Scheme:

```(use-modules (ice-9 match))

(define (partial-products lst)
(match lst
(() (list))
(cons (apply * tail)
(map (lambda (e) (* head e))
(partial-products tail))))))
```
11. programmingpraxis said

@Bavier: Very nice!

12. David Liu said

My solution:

array1 = [5, 3, 4, 2, 6, 8]
array2 = []

length = len(array1)

for i in range(length):

``````val = 0

for j in range(length):
if i != j:
if val == 0:
val = array1[j]
else:
val = val*array1[j]

array2.append(val)
``````

print(array2)

13. Jim Li Chong said

``` import java.util.*; class partial_array_product { public static void main(String args[]) { Scanner in = new Scanner(System.in); System.out.println("Please enter the size of your array : "); int k = in.nextInt(), arr[] = new int[k], product = 1;```

``` System.out.println("Please enter elements of the array : "); for(int i = 0; i < arr.length; i++) arr[i] = in.nextInt(); for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr.length; j++) if (arr[j] != arr[i]) product *= arr[j]; System.out.println("The product excluding " + arr[i] + " is " + product); product = 1; } } ```

```} ```