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));

ruby的解决方案

a = [1,2,3,4]
result = []
a.each {|x| result.push( (a-[x]).reject(&:zero?).reduce(:*)) }
puts result

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

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));

这是我的代码:

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

以下是线性O(n)时间内的简单Scala版本:

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

}

这是可行的，因为本质上答案是一个数组，它是左右所有元素的乘积。