Sum of all substrings of an array of integers
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 a new array. In this case, the amount is 2333. Please help find a solution c O(n)
. My solution O(n^2)
doesn't work.
the link to the problem is here or here .
My current attempt (while searching for a pattern)
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 on the right) C weight. (combination {of permutation and combination)) 2 ^ i = 2 cardinality (number of integers to the left)
thank
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's simple. Let's say we want to calculate the sum of all subparts {1,3,5,7}. Suppose we know the number of combinations {1,3,5} and the sum of the subpart {1,3,5}, and we can easily calculate {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 obtained by observation. Let's say we have any combination {1,3,5}
A = [135, 13, 15, 35, 1, 3, 5]
We can easily create a list {1,3,5,7} with
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]
Well, you can look at subparts as sums of numbers:
1357 = 1000*1 + 100*3 + 10*5 + 1*7
135 = 100*1 + 10*3 + 1*5
137 = 100*1 + 10*3 + 1*7
etc..
So, all you have to do is add the numbers you have, and then, according to the number of elements, figure out what the factor is:
Two numbers [x, y]
:
[x, y, 10x+y, 10y+x]
=> your multiplier is 1 + 10 + 1 = 12
Three numbers [x, y, z]
:
[x, y, z,
10x+y, 10x+z,
10y+x, 10y+z,
10z+x, 10z+y,
100x+10y+z, 100x10z+y
.
. ]
=> your multiplier is 1 + 10 + 10 + 1 + 1 + 100 + 100 + 10 + 10 + 1 + 1 = 245
You can easily work out an equation for numbers n
....
If you expand the invisal recursive solution, you get this explicit formula:
subpart sum = sum for k=0 to N-1: 11^(N-k) * 2^k * a[k]
This suggests the following O (n) algorithm:
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
Multiplication and addition must be done modulo M. Of course.