Solving the Plus Minus problem in Python
By John Lekberg on July 09, 2020.
This week's blog post is about solving the "PlusMinus" problem in Python. You will learn:
 How to create a brute force solution using the itertools and operator modules.
 How to create a more efficient solution by noticing hidden structure within the problem.
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 2^{n} 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 2^{n})
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:

Start with
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 nth 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
andunsigned_nums
takes O(n) steps.
 Creating the iterator
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 "PlusMinus" 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.)