32
4
A set is sum-free if no two (not necessarily distinct) elements when added together are part of the set itself.
For example, {1, 5, 7}
is sum-free, because all members are odd, and two odd numbers when added together are always even. On the other hand, {2, 4, 9, 13}
is not sum-free, as either 2 + 2 = 4
or 4 + 9 = 13
add together to a member of the set.
Write a program or function that takes a set as input, and outputs a Truthy value if the set is sum-free, and Falsy otherwise.
Examples:
Sum-free:
{}
{4}
{1, 5, 7}
{16, 1, 4, 9}
Not sum-free:
{0}
{1, 4, 5, 7}
{3, 0}
{16, 1, 4, 8}
Can the set be an array/list? – Conor O'Brien – 2016-07-07T01:05:03.233
@CᴏɴᴏʀO'Bʀɪᴇɴ Sure. – orlp – 2016-07-07T01:17:24.080
Related and related. – FryAmTheEggman – 2016-07-07T01:32:04.917
@FryAmTheEggman Except for
{0}
... – feersum – 2016-07-07T01:47:05.623@FryAmTheEggman No clarification is necessary, you can logically derive that the empty set is sum free (no two elements when added together are part of the set itself, in fact, nothing is part of the set), and that any set containing one element is sum-free, except for
{0}
, as 0+0 is in the set. – orlp – 2016-07-07T01:51:33.5505Some more test cases might be nice! – Lynn – 2016-07-07T01:52:53.230
4Badly needs test cases. Are sets purely unique? – cat – 2016-07-07T02:33:55.710
I'd be interested in your motivation for this concept. There's a related concept that you may or may not find more useful; let X denote a closure system. Call a subset A of X minimalistic iff for all proper subsets B of X, we have that cl(B) is a proper subset of cl(A). In other words, A is minimalistic iff it is minimal among those sets that generate its closure. Now make the set of natural numbers into a closure system as follows: if A is a subset of Nat, then cl(A) is the intersection of all subsets of Nat that include A and are closed under addition and 0. Question: is a subset – goblin – 2016-07-07T05:16:38.757
... of Nat is minimalistic with respect to this closure operator? Its clear that minimalistic implies sum-free. On the other hand {2,6} is an example of a sum-free set that isn't minimalistic. Here's the wikipedia link about closure systems.
– goblin – 2016-07-07T05:18:21.640is
[0,1]
sum free, not sum free, or undefined? (I.e.: what about repeats?) – Titus – 2016-07-07T07:50:36.607@Titus
0+1 = 1
, which is in the set, so, not sum free – Lulhum – 2016-07-07T07:59:55.880@Lulhum That only applies if repeats are allowed. And that was my actual question. update: I just saw that orlp already has answered my question to FryAmTheEggman. – Titus – 2016-07-07T08:31:22.000
Can we assume the input is sorted? – Martin Ender – 2016-07-07T08:39:02.377
@MartinEnder No. Sets are unordered without duplicates. You may take an array, tuple, etc, but not assume that it is sorted. – orlp – 2016-07-07T13:57:00.887
@orlp can you please update the question with some (lots) more test cases and clear spec and explanations about empty, length-1 and the
{ 0 1 }
sets? – cat – 2016-07-07T18:02:48.390@cat The spec is clear. Examples I can add. – orlp – 2016-07-07T18:22:01.113
2+2=4 cannot be a valid addition in the set {2,4,9,13} as it has utilised two 2s. Or are duplicates allowed. And in that case {0} is sum free surely? – george – 2016-07-08T18:16:39.787
@george Adding the same element to itself is allowed. And
{0}
is not sum-free precisely for that reason: 0 + 0 = 0. – orlp – 2016-07-08T18:43:15.3803I think you should clarify that you mean the sum of two not necessarily distinct elements from the set. – Gregory Nisbet – 2016-07-09T00:32:21.417
Is this a NP-complete problem? – palsch – 2016-07-10T10:19:24.047
@palsch No, it's a O(n^2) simple loop. – orlp – 2016-07-10T19:30:17.300