arrays - 整数数组所有子部分的总和

Question

给定一个数组{1,3,5,7}，它的子部分定义为{1357,135,137,157,357,13,15,17,35,37,57,1, 3,5,7}。我必须在新数组中找到所有这些数字的总和。在这种情况下，总和为 2333。请帮助我在O(n) 中找到解决方案。我的 O(n^2) 解决方案超时。

问题的链接是here或 here .

我目前的尝试(寻找模式)是

for(I=0 to len) //len is length of the array
{
     for(j=0 to len-i)
     {
          sum+= arr[I]*pow(10,j)*((len-i) C i)*pow(2,i)
     }
}

换言之 - len-i C i =(右边的整数个数)C 权重。 (组合{来自排列组合})2^i = 2 次方(左边的整数个数)

谢谢

Answer 1

您可以使用简单的递归轻松解决此问题。

def F(arr):
    if len(arr) == 1:
        return (arr[0], 1)
    else:
        r = F(arr[:-1])
        return (11 * r[0] + (r[1] + 1) * arr[-1], 2 * r[1] + 1)

那么，它是如何工作的呢？很简单。假设我们要计算 {1,3,5,7} 的所有子部分的总和。假设我们知道 {1,3,5} 的组合数和 {1,3,5} 子部分的总和，我们可以使用以下公式轻松计算 {1,3,5,7}:

SUM_SUBPART({1,3,5,7}) = 11 * SUM_SUBPART({1,3,5}) + NUMBER_COMBINATION({1,3,5}) * 7 + 7

这个公式很容易通过观察推导出来。假设我们有 {1,3,5}

的所有组合

A = [135, 13, 15, 35, 1, 3, 5]

我们可以很容易地创建一个 {1,3,5,7} 的列表

A = [135, 13, 15, 35, 1, 3, 5] + 
    [135 * 10 + 7, 
     13  * 10 + 7, 
     15  * 10 + 7, 
     35  * 10 + 7, 
     1   * 10 + 7, 
     3   * 10 + 7, 
     5   * 10 + 7] + [7]