# Solving the Plus Minus problem in Python

By John Lekberg on July 09, 2020.

This week's blog post is about solving the "Plus-Minus" problem in Python. You will learn:

# Problem statement

You are given a positive number n. Your goal is to find a way to add and subtract the numbers from 1 to n to make 0.

E.g. n = 4 and a solution is

0 = 1 - 2 - 3 + 4

For a given n it may be impossible to find a solution.

# How I represent the data in the problem

I represent the solution as a list of the numbers 1 to n, each number being positive or negative (to represent addition or subtraction). E.g. the solution "1 - 2 - 3 + 4" is represented as

``````[1, -2, -3, 4]
``````

If a solution cannot be found, I use the value None.

# Creating a brute force solution

A simple brute force solution will attempt every possible way to add and subtract the numbers. Here's a Python function that does that:

``````from itertools import product
from operator import pos, neg

def plus_minus_bf(*, n):
"""Solve the 'Plus Minus' problem using brute force."""
assert n > 0
unsigned_nums = range(1, n + 1)
for signs in product([pos, neg], repeat=n):
signed_nums = [
sign(num)
for sign, num in zip(signs, unsigned_nums)
]
if sum(signed_nums) == 0:
return signed_nums
``````

This code starts with a range of unsigned numbers and "signs" the numbers by using operator.pos and operator.neg. The code uses itertools.product to generate all possible ways to mark the numbers in `unsigned_nums` as positive (being added) or negative (being subtracted). Here are solutions for n = 1 to n = 10.

``````print("n   Solution")
print("--  --------")
for i in range(1, 11):
print(f"{i:2}  {plus_minus_bf(n=i)}")
``````
``````n   Solution
--  --------
1  None
2  None
3  [1, 2, -3]
4  [1, -2, -3, 4]
5  None
6  None
7  [1, 2, -3, 4, -5, -6, 7]
8  [1, 2, 3, 4, -5, -6, -7, 8]
9  None
10  None
``````

What's the time complexity of this function? For a positive integer n:

• There are 2n ways to add and subtract the numbers 1 to n.
• Signing the unsigned numbers and checking that the signed numbers sum to 0 takes O(n) operations, because the list of n numbers is looped over.

As a result, the overall time complexity of the function is

O(n 2n)

# Creating a more efficient solution

To create a more efficient solution, I look more closely at the structure of the problem:

• I have the numbers 1 to n.

• Consider any 4 consecutive numbers

i, i+1, i+2, i+3

• It's true that

(i) - (i+1) - (i+2) + (i+3) = 0

I call this the pattern.

As a result, I can solve the problem if n = 4k:

• Repeat the pattern k times to cover all the numbers from 1 to n.
• The additions and subtractions will total to 0.

And I can solve the problem if n = 4k+3:

-1 - 2 + 3 ...

(This totals to 0.)

• Repeat the pattern k times to cover all the numbers from 1 to n.

• The additions and subtractions will total to 0.

But, what if n = 4k+1 or n = 4k+2? There is no solution. Here's why:

• For a given n, I want to divide the numbers 1 to n into two sets, the pluses P and the minuses M, so that

sum(P) - sum(M) = 0

• This means that

sum(P) + sum(M) = 2 sum(M)

• As a result,

sum(P) + sum(M) is even

• The numbers 1 to n are divided between P and M, so

sum(P) + sum(M) = 1 + 2 + ... + n

• This sum is called the n-th triangular number and has a closed form expression

1 + 2 + ... + n = n(n + 1)/2

• As a result,

sum(P) + sum(M) = n(n + 1)/2

• Because

sum(P) + sum(M) is even

then

n(n + 1)/2 must be even

• As a result,

n(n + 1)/2 must be divisible by 2

This implies that

n(n + 1) must be divisible by 4

• As a result,

n or n + 1 is divisible by 4

And this is only true when

n = 4k

or when

n = 4k + 3

• This means that there is no solution when

n = 4k + 1

or when

n = 4k + 2

Here's a Python function that implements this faster algorithm:

``````from itertools import cycle, chain
from operator import pos, neg

def plus_minus_fast(*, n):
"""Efficiently solve the 'Plus Minus' problem."""
assert n > 0

rem = n % 4
if rem == 1 or rem == 2:
return None

pattern = [pos, neg, neg, pos]
if rem == 0:
signs = cycle(pattern)
elif rem == 3:
signs = chain([neg, neg, pos], cycle(pattern))

unsigned_nums = range(1, n + 1)
signed_nums = [
sign(num) for sign, num in zip(signs, unsigned_nums)
]
return signed_nums
``````

This code uses itertools.cycle and itertools.chain to construct the sequence of signs. `cycle()` actually creates an infinite iterator, but this isn't a problem because zip truncates the iterator to the length of `unsigned_nums`.

Here are solutions for n = 1 to n = 10.

``````print("n   Solution")
print("--  --------")
for i in range(1, 11):
print(f"{i:2}  {plus_minus_fast(n=i)}")
``````
``````n   Solution
--  --------
1  None
2  None
3  [-1, -2, 3]
4  [1, -2, -3, 4]
5  None
6  None
7  [-1, -2, 3, 4, -5, -6, 7]
8  [1, -2, -3, 4, 5, -6, -7, 8]
9  None
10  None
``````

What's the time complexity of this algorithm? For a positive integer n:

• If n = 4k+1 or n = 4k+2, then the function immediately returns, taking O(1) steps.
• Otherwise, n = 4k or n = 4k+3.
• Creating the iterator `signs` takes O(1) steps.
• Iterating over `signs` and `unsigned_nums` takes O(n) steps.

As a result, the overall time complexity of the algorithm is

O(n)

# In conclusion...

In this week's post, you learned how to solve the "Plus-Minus" problem. You learned how to create a brute force solution using the itertools and operator modules. And you learned how to create a more efficient solution by noticing hidden structure in the problem.

My challenge to you:

You are given positive numbers n and m. Write a program that finds a way to add and subtract the numbers from 1 to n to make m.

If you enjoyed this week's post, share it with your friends and stay tuned for next week's post. See you then!

(If you spot any errors or typos on this post, contact me via my contact page.)