CODEWITHSUNDEEP
python
Josephi Dmitry
Josephi Dmitry

Reputation: 61

Addition of numbers from a list

For this question I'm trying to add together integers from a list.

For example, if the inputted numbers are [2,4,6], it should output 34 because (1+2)+(1+2+3+4)+(1+2+3+4+5+6) = 34.

If the input is [9], it will output 45; (1+2+3+4+5+6+7+8+9) = 45.

Here's my code:

def additionOfList(st):
    n = len(st)
    total = 0

    for i in range(n):
        for k in range(1, n+1):
            total += k

    return total

Any help would be greatly appreciated; can't seem to figure this out.

Upvotes: 0

Views: 848

Answers (3)

Martijn Pieters
Martijn Pieters

Reputation: 1121894

You are summing triangle numbers; just define a function that calculates the triangle number for each entry, then use sum() to sum each result.

Triangle numbers can be calculated trivially with the formula (N * (N + 1)) / 2:

def triangle_number(n):
    return (n * (n + 1)) // 2

def triangle_sum(l):
    return sum(map(triangle_number, l))

Your own error is to use the length of the input list as n; you are not calculating the triangle number of the length of the list; you'd want to use each individual number in st as n here:

def additionOfList(st):
    total = 0
    for n in st:
        # calculate triangle number for n

However, whatever you do, do not just loop from 1 to n! That won't scale to large numbers, and is not needed here at all.

If you want to understand why triangle numbers can so easily be calculated, just write out the numbers on a line. Lets use n = 5:

1 2 3 4 5

Now write the same numbers in reverse underneath, and add up the columns:

1 2 3 4 5
5 4 3 2 1 +
----------
6 6 6 6 6

The sum is always 6. That's no coincidence. When you increase N, the sum is always going to be N + 1. Now add up the numbers on the bottom column, that's just 5 times 6, right?

1 2 3 4 5
5 4 3 2 1 +
----------
6 6 6 6 6 = 5 x 6 = 30

So the sum of all numbers from 1 to 5 plus the sum of numbers of 5 to 1, is 5 times 5 + 1. That's double from what you needed for 1 to 5 alone. Since it is doubled only because you also added 5 through to 1, you can divide by 2 to get the sum:

1 2 3 4 5 = 5 x 6 / 2 = 15
5 4 3 2 1 = 5 x 6 / 2 = 15
----------
6 6 6 6 6 = 5 x 6 = 30

Generalising that to any N, that makes:

triangle_number(N) = N * (N + 1) / 2

Since we can calculate that number for any N, it'll always be faster than manually adding up 1 + 2 + 3 + 4 + ... + N. Computers like that kind of trick.

You can ask Python to sum all the numbers from 1 through to N with:

sum(range(1, n + 1))

but if you compare that with the above triangle_number() function, you'll find that it can take a long, long time when your n value becomes big:

>>> def triangle_number(n):
...     return (n * (n + 1)) // 2
...
>>> def sum_range(n):
...     return sum(range(1, n + 1))
...
>>> triangle_number(5)
15
>>> sum_range(5)
15
>>> from timeit import timeit
>>> timeit('c(1000)', 'from __main__ import sum_range as c')  # how long does it take to do this 1 million times
17.520909604994813
>>> timeit('c(1000)', 'from __main__ import triangle_number as c')
0.1906668500159867

1 million calculations of the triangle number for N = 1000 is really fast, but summing 1 through to 1000 takes 17.5 seconds.

Upvotes: 3

Conner
Conner

Reputation: 31050

l = [2,4,6]
total = 0

for i in l:
    summation = (i * (i + 1)) / 2
    total = total + summation

print(total) # 34

or... for the one-liner folks

print(sum([(i*(i+1))/2 for i in [2,4,6]]))

Upvotes: 6

Filip Młynarski
Filip Młynarski

Reputation: 3612

def additionOfList(st):
    return int(sum([(i**2)/2 + i/2 for i in st]))

print(additionOfList([2,4,6])) # -> 34

Upvotes: 1

Related Questions