时间戳

首页 > 解决方案 > js中N可以表示为K因子乘积的方式数

javascript - js中N可以表示为K因子乘积的方式数

问题描述

给出一个数字 N，一个包含所有因子的数组，一个数字 K...我们需要找到可以将 N 表示为 K 个因子的乘积的多种方式，即如果

N=64
K=3
arr = [1,2,4,8,16,32,64]

所以方法的数量是 7 因为

1x1x64=64
1x2x32=64
1x4x16=64
1x8x8=64

等等

标签： javascriptarraysnode.jsalgorithmsorting

解决方案

要从数组中获取长度为 的组合，k我们可以使用递归生成器：

function* combinations(array, k, i = 0, prepend = []) {
  if(!k) {
    yield prepend;
  } else {
    while(i < array.length)
      yield* combinations(array, k - 1, i /*+ 1*/, prepend.concat(array[i++]));
 }
}

（注释掉的 +1 是为了排除重复项（1 * 1 * 1），但 OP 似乎不需要这种行为）

因此，要获得所有组合，我们可以这样做：

[...combinations([1, 2, 3, 4], 2)] // [1, 2], [1, 3] ...

现在我们只需要将它们相乘：

const multiply = array => array.reduce((a, b) => a * b);

并过滤掉那些是 N 的：

[...combinations(arr, K)].filter(el => multiply(el) === N).length

这将返回7。

PS：是的，有更简单、更快捷的方法，但我有时只想使用一些罕见（但很酷）的语言特性 :)

推荐阅读