How to square and sum only positive integers in array without using loop or comprehension?

Question

Here is my array :

[3, -1, 1, 14]

I want to square only positive elements and sum them without using any loop or list / set / dictionary comprehension. However standard library packages can be used.

Note:-The elements in list can rage between -100 to +100

i think recursion can be use to move through list, but it will be quite a bit less efficient. It can also fail on long lists, when Python hits the system recursion limit (which is 1000, by default).

Answer 1

List comprehensions can be seen as syntactic sugar for functions that take functions such as map, filter and reduce. For example:

[f(x) for x in xs]

is the same as

list(map(f,xs)

and

[x for x in xs if x>0]

is identical to

list(filter(lambda x:x>0, xs))

Ch3steR's answer in the comments above is

sum([x*x if x>0 else 0 for x in xs])

The sugar-less equivalent of this is

xs = [3,-1,1,14]
sum(map(lambda x: x*x if x>0 else 0, xs))

Maybe for clarity we can remove lambdas:

def square_if_pos(x):
    if x>0:
        return x*x
    if x<=0:
        return 0

xs = [3,-1,1,14]
answer = sum(map(square_if_pos, xs))

Another valid answer with list comprehensions would be

sum([x*x for x in xs if x>0])

which, without the syntax sugar is equivalent to

answer = sum(map(square_if_pos,filter(lambda x:x>0, xs))))

or maybe without so many parentheses:

positive_numbers = filter(lambda x: x>0, xs)
positive_squares = map(lambda x: x*x, positive_numbers))
answer = sum(positive_squares)

Both answers are equivalent because summing a list with some zeros or removing those zeros is the same thing: x+0 == x. Maybe for long enough lists, the solution with filter is more efficient.

---

Edit: I had misunderstood a comment above as being a full answer

Answer 2

You could use reduce from functools:

from functools import reduce

L = [3, -1, 1, 14]

R = reduce(lambda a,b:a+b*b*(b>0),L,0)

print(R) # 206

If the "them" in "I want to square only positive elements and sum them" refers to all numbers (not only the squared one), you can write it like this:

R = reduce(lambda a,b:a+b*b**(b>0),L,0)

print(R) # 205

Answer 3

I mean it is not the most efficient, but it surely works with recursion:

def sum_and_square(arr, left, right):
    if left == right:
        if arr[left]>0:
            return arr[left]**2
        else:
            return 0;
    
    mid = int(left + (right-left) / 2)
    return sum_and_square(arr, left, mid) + sum_and_square(arr, mid+1, right)
    
l = [1, 2, -3, -4] * 1000000
sum_and_square(l, 0, len(l)-1)

Answer 4

Poster: "i think recursion can be use to move through list, but it will be quite a bit less efficient."

Actually, this issue can be solved by using recursion by reducing the list size by half at each recursion rather than 1.

def sum_square(x):
    if not x:
        return 0
    if len(x) == 1:
        return x[0]*x[0] if x[0] > 0 else 0
    
    # Split array in half, and recurse on two halves
    # This limits recursion depth for list of length n to log2(n)
    # rather than n
    n = len(x) // 2
    return sum_square(x[:n]) + sum_square(x[n:])

Test

Test 1: Posted List

a = [3,-1,1,14]
>>> sum_square(a)
206

Test 2: large list

from random import randint

# Create large list
a = [randint(-100, 100) for _ in range(10000000)]

>>>sum_square(a)
169445030

Answer 5

As you were told not to use loops and sum a list, there is no other way than use streams with functional tools that are built in python

Use map(func, *iterables) to compute the sum for a given list

As far as you want to square only positive numbers your function will look like

def square(x: int):
    if x > 0:
        return x * x
    else:
        return 0

Or you can rewrite that as a lambda function with ternary operator

lambda x: x * x if x > 0 else 0

Then map function will look like this

map(lambda x: x * x if x > 0 else 0, arr)  # [9, 0, 1, 196]

And then use sum(*iterable) function to sum up the result of an array

sum(map(lambda x: x * x if x > 0 else 0, arr))

Answer 6

Since you didn't rule out generator expressions:

sum(x * x for x in xs if x > 0)

Answer 7

Consider that (what follows is math and by ^ I mean power, which is ** in Python)

x^2 + y^2 == (x+y)^2 - 2*x*y

and

(x+y+z)^2 = ((x+y)+z)^2 = x^2 + 2xy + y^2 + 2*(x+y)*z + z^2

by induction it can be shown that

(x_1 + x_2 + ... + x_n)^2 = 2*x_1 x_2 + 2*(x_1+x_2)*x_3 + ... 2*(x_1+...x_n)*x_n + x_1^2 + ... + x_n^2

Then the sum of squares is the square of the sum plus twice the following

x_1*x_2 + (x_1+x_2)*x_3 + (x_1+... x_n)*x_n

So what we need to do is accumulate the partial sums x_1, x_1+x_2, etc. in a list and then "zip with" the elements of the list itself.

Let's make this Python again.

from itertools import accumulate

def square(x):
    return x*x
def plus(x,y):
    return x+y
def times(x,y):
    return x*y


xs = [3, 1, -1, 14]
xs = list(filter(lambda x: x>0, xs)) # I wish we could avoid this so early

# either this or change square to lambda x:x*x if x>0 else 0
squared_sum = square(sum(xs))
partial_sums = accumulate(xs, plus)
missing_part = 2*sum(map(times, partial_sums, xs[1:]))

answer = squared_sum - missing_part

and there you have it. (I'm still hoping for an algebraic solution that avoids having to filter the list, though.)