{-
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)*c*sqrt(n) + c*sqrt(n) + n
    ≤ c*n + c*sqrt(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)

下面是我用现代c++编写的解决方案。它使用std::transform，很容易记住。

在线代码(wandbox)。

#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 << " "; 
}

下面是Ruby中的一行程序解决方案。

全国矿工工会。映射{|n| (num - [n]).inject(:*)}

这是O(n²)但f#太漂亮了

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]

在这里添加我的javascript解决方案，因为我没有发现任何人建议这样做。 除法是什么，除了数从另一个数中得到一个数的次数吗?我计算了整个数组的乘积，然后遍历每个元素，并减去当前元素直到0:

//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;
}

使用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)

使用Node.js v4.4.5运行:

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 ]