CMPUT 275 - Tangible Computing
Morning Problem: Missing Multipliers
Description
Bob loves multiplying numbers! He wants to try something new though. Bob wants to
multiply a list of numbers excluding a specific section of them.
To be specific, if Bob has a list of n integers, he wants to know for each integer ai
in his list,
what would be the product if he multiplied everything except for ai and the numbers within
m spaces of ai
.
For example, take the array [1, 2, 3, 4, 5], if m = 1 the output would be [60, 20, 5, 2, 6],
3 ∗ 4 ∗ 5 = 60, 4 ∗ 5 = 20, 1 ∗ 5 = 5, 1 ∗ 2 = 2, 1 ∗ 2 ∗ 3 = 6.
Input
On the first line of input you will be given two space separated integers n, (1 ≤ n ≤ 100, 000),
the amount of numbers in the array, and m, (0 ≤ m ≤ n − 1), the amount of multipliers to
be excluded from the product on either side of each ai
.
On the second line you will be given n space separated integers, such that for each ai
,
(−10 ≤ ai ≤ 10) and Qn−1
i=0 |ai
| ≤ 2
63 − 1.
Output
You are to output one line containing n space separated integers, each ai should be the
product of the array excluding itself and it’s m neighbours to the left and right (if such
neighbours exist), if all digits are excluded you are to put an answer of 0 (see sample 2).
Sample Input 1
3 0
3 -4 7
Sample Output 1
-28 21 -12
Explanation:
With m = 0 we only worry about the product without ai
, so we get -4 ∗ 7 = -28, 3 ∗ 7 =
21, and 3 ∗ -4 = -12.
Sample Input 2
5 2
3 -2 7 0 4
Sample Output 2
0 4 0 3 -6
Explanation:
With m = 2 things get a bit more complicated, we get 0 ∗ 4 = 0, 4 because it is the only
multiplier, 0 because there are no multipliers, 3 because it is the only multiplier, and 3 ∗ -2
= -6.
