CODEWITHSUNDEEP
pythonpython-3.x
Negativ3
Negativ3

Reputation: 62

Computing a nested sum in python

I am new to programming and to python so I want to ask you guys a simple way to compute a double sigma by programming

(∑ni=1)(∑mk=1)(i+k)

I am trying to solve the problem but I'm stuck on the part where I need to initialize p any Hints will be appericiated.

here is what I tried so far

p = 1
sum = 0

N,M=[int(i) for i in input().split()]
for i in range(1,N+1):
    for i in range(i+1,i+M+1):
        p=p*i
    sum += p

print(sum)

Upvotes: 1

Views: 809

Answers (2)

Eli Korvigo
Eli Korvigo

Reputation: 10513

Consider the following:

enter image description here

This means your naïve quadratic O(m*n) algorithm can be replaced with a linear O(m+n) solution:

In [1]: from hypothesis import strategies as st
   ...: from hypothesis import given, settings
   ...: 
   ...: 
   ...: def linear(n, m):
   ...:     return n * sum(range(1, m+1)) + m * sum(range(1, n+1))
   ...: 
   ...: 
   ...: def quadratic(n, m):
   ...:     total = 0
   ...:     for i in range(1, n+1):
   ...:         for j in range(1, m+1):
   ...:             total += i + j
   ...:     return total
   ...: 
   ...: 
   ...: @given(st.integers(1, 50), st.integers(1, 50))
   ...: @settings(max_examples=1000)
   ...: def test(n, m):
   ...:     assert linear(n, m) == quadratic(n, m)
   ...: 
   ...:     

In [2]: test()

In [3]: %timeit linear(10, 10)
852 ns ± 15.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In [4]: %timeit quadratic(10, 10)
7.93 µs ± 165 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Since you are a beginner, I've added a simple automatic property test to: 1) emphasise the importance of testing a working naïve solution vs an optimised alternative, 2) demonstrate the equivalence. A couple of benchmarks for small n and m are also there.

And since there is a closed-form equation for sums of arithmetic series (i.e. M and N), you can further boil this down to a constant time O(1) solution (I've done a fair bit of simplification here):

In [5]: def constant(n, m):
   ...:     return n * m * (2 + m + n) / 2
   ...: 
   ...: 

In [6]: %timeit constant(10, 10)
151 ns ± 1.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

P.S.

You should never shadow a built-in name (e.g. sum = 0) in the global name-space without a very good reason for that.

Upvotes: 4

jbndlr
jbndlr

Reputation: 5210

Following your approach (not runtime optimized), you need to reset your p variable denoting your inner product in each run of your sum; thus set it to 1 at the beginning of each outer loop:

sum = 0

N,M=[int(i) for i in input().split()]
for i in range(1,N+1):
    p = 1
    for i in range(i+1,i+M+1):
        p=p*i
    sum += p

print(sum)

With this approach and the domains given in your exercise, you will not be able to compute it for higher numbers in the given time constraint. You may want to optimize this.

Upvotes: 1

Related Questions