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

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) 解决方案超时。

link问题是here or 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

好吧，您可以将子部分视为数字的总和：

 1357 = 1000*1 + 100*3 + 10*5 + 1*7  
 135 =  100*1  + 10*3  + 1*5  
 137 =  100*1  + 10*3  + 1*7

等..

所以，你需要做的就是将你拥有的数字相加，然后根据项目的数量计算出乘数是多少：

两个数字[x, y]：

 [x, y, 10x+y, 10y+x]

=> 你的乘数是 1 + 10 + 1 = 12

三个数字[x, y, z]:

[x, y, z, 
 10x+y, 10x+z, 
 10y+x, 10y+z, 
 10z+x, 10z+y, 
 100x+10y+z, 100x10z+y
 .
 . ]

=> 你的乘数是 1+10+10+1+1+100+100+10+10+1+1=245

您可以轻松计算出 n 个数字的等式....

Answer 2

你可以通过简单的递归轻松解决这个问题。

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]

Answer 3

如果你展开 invisal 的递归解，你会得到这个明确的公式：

subpart sum = sum for k=0 to N-1:  11^(N-k) * 2^k * a[k]

这表明以下 O(n) 算法：

multiplier = 1
for k from 0 to N-1:
    a[k] = a[k]*multiplier
    multiplier = multiplier*2

multiplier = 1
sum = 0
for k from N-1 to 0:
    sum = sum + a[k]*multiplier
    multiplier = multiplier*11

当然应该对乘法和加法取模 M。

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

Sum of all subparts of an array of integers

arrays

algorithm

big-o

sum

subset