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.
Programming Praxis 
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)Haskell also has
scanr. Here’s my golfed version: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[0] = products_array[1]; 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; }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.
Here’s a solution in x86 assembly.
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.
<
pre>
array:
[5, 3, 4, 2, 6, 8]
partial_products(array):
[1152, 1920, 1440, 2880, 960, 720]
<
pre>
Here’s the output again, hopefully formatted properly this time:
In Ruby.
def partial_product(array) array.each_with_index.map do |_, i| array.rotate(i).drop(1).reduce(&:*) end endPython 3, in the REPL.
a simple java solution below ..
//package com.mayank.randompractice;
import java.util.*;
public class CodeDay1_IDZ {
}
Simple recursive solution in Guile Scheme:
(use-modules (ice-9 match)) (define (partial-products lst) (match lst (() (list)) ((head tail ...) (cons (apply * tail) (map (lambda (e) (* head e)) (partial-products tail))))))@Bavier: Very nice!
My solution:
array1 = [5, 3, 4, 2, 6, 8]
array2 = []
length = len(array1)
for i in range(length):
print(array2)
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;
}