Given an array `{1,3,5,7}`

, its subparts are defined as `{1357,135,137,157,357,13,15,17,35,37,57,1,3,5,7}`

. I have to find the sum of all these numbers in the new array. In this case sum comes out to be 2333. Please help me find a solution in `O(n)`

. My `O(n^2)`

solution times out.

link to the problem is here or here.

My current attempt( at finding a pattern) is

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

In words - len-i C i = (number of integers to right) C weight. (combinations {from permutation and combination}) 2^i = 2 power (number of integers to left)

Thanks

# Best How To :

You can easily solve this problem with a simple recursive.

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

So, how does it work? It is simple. Let say we want to compute the sum of all subpart of {1,3,5,7}. Let assume that we know the number of combinatiton of {1,3,5} and the sum of subpart of {1,3,5} and we can easily compute the {1,3,5,7} using the following formula:

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

This formula can easily be derived by observing. Let say we have all combination of {1,3,5}

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

We can easily create a list of {1,3,5,7} by

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