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

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)的解法超时了。

问题链接在这里或这里。

我目前的尝试（寻找模式）是：

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 weight。其中，组合来自排列和组合。 2 ^ i = 2的（左侧整数的数量）次方。

谢谢。

- the_coder

---

请注意数组的长度可能很大。有没有关于如何在考虑时间复杂度的情况下解决问题的提示？ - the_coder

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,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]

- invisal

---

非常感谢！:D 不错的方法。 - the_coder

Answer 2

嗯，你可以把子部分看作是数字之和：

 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个数字的方程式...

- shapiro yaacov

---

乘数不会对所有数字都相同，因为不允许重新排序。看到7总是在最后一位了吗？ - Joni

一个问题，对于两个数字 - [x，y]..我们得到：[x，y，10x + y]..我们没有10y + x，或10z + x，或10z + y等等。我试图制定一个模式，但我无法制定O（n）模式。我的当前模式是O（n ^ 2）。 - the_coder

@Joni - 你是正确的。我以为我们在处理所有选项。无论如何，这仍然可以针对每个数字进行处理。 - shapiro yaacov

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下执行。

- Joni