37
\$\begingroup\$

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}
\$\endgroup\$
21
  • \$\begingroup\$ Can the set be an array/list? \$\endgroup\$ Jul 7, 2016 at 1:05
  • \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ Sure. \$\endgroup\$
    – orlp
    Jul 7, 2016 at 1:17
  • 6
    \$\begingroup\$ Some more test cases might be nice! \$\endgroup\$
    – Lynn
    Jul 7, 2016 at 1:52
  • 5
    \$\begingroup\$ Badly needs test cases. Are sets purely unique? \$\endgroup\$
    – cat
    Jul 7, 2016 at 2:33
  • 5
    \$\begingroup\$ I think you should clarify that you mean the sum of two not necessarily distinct elements from the set. \$\endgroup\$ Jul 9, 2016 at 0:32

44 Answers 44

1
2
1
\$\begingroup\$

Prolog (SWI), 66 56 49 bytes

A/B:-member(A,B).
-L:- \+ (E/L,F/L,G is E+F,G/L).

Try it online!

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 6 4 bytes

âOмQ

Try it online or verify all test cases.

Explanation:

â       # Take all pairs of the input-list
        #  i.e. [1,5,7] → [[1,1],[1,5],[1,7],[5,1],[5,5],[5,7],[7,1],[7,5],[7,7]]
        #  i.e. [1,4,5] → [[1,1],[1,4],[1,5],[4,1],[4,4],[4,5],[5,1],[5,4],[5,5]]
 O      # Sum all pairs
        #  i.e. [[1,1],[1,5],[1,7],[5,1],[5,5],[5,7],[7,1],[7,5],[7,7]]
        #    → [2,6,8,6,10,12,8,12,14]
        #  i.e. [[1,1],[1,4],[1,5],[4,1],[4,4],[4,5],[5,1],[5,4],[5,5]]
        #    → [2,5,6,5,8,9,6,9,10]
  м     # Remove all values in the input-list that are also in the list above
        #  i.e. [1,5,7] and [2,6,8,6,10,12,8,12,14] → ['1','5','7']
        #  i.e. [1,4,5] and [2,5,6,5,8,9,6,9,10] → ['1','4','']
   Q    # Is the current list still equal to the input-list?
        #  i.e. [1,5,7] and ['1','5','7'] → 1
        #  i.e. [1,4,5] and ['1','4',''] → 0
\$\endgroup\$
1
\$\begingroup\$

Husk, 8 7 6 bytes

¬Sn´×+

Try it online!

-1 byte from Zgarb.

Same method as the Pyth solution.

Explanation

¬Sn´×+ implicit input
   ´   double: ´ f x = f x x
    ×+ map sum to all pairs
 S     hook: S f g x = f x (g x)
  n    intersection of sums with input
¬      negate
\$\endgroup\$
2
  • \$\begingroup\$ You can use × instead of ΣṪ. \$\endgroup\$
    – Zgarb
    Oct 4, 2020 at 19:11
  • \$\begingroup\$ @Zgarb added it in.. \$\endgroup\$
    – Razetime
    Oct 7, 2020 at 12:18
1
\$\begingroup\$

Scala 3, 52 37 bytes

Saved 15 bytes using lambda function.


s=>s==s.diff(for{a<-s;b<-s}yield a+b)

Attempt This Online!

\$\endgroup\$
1
  • \$\begingroup\$ Why not make it a lambda? Would save a few bytes \$\endgroup\$
    – user
    May 11, 2023 at 3:17
1
\$\begingroup\$

Thunno 2 !, 3 bytes

Ṗʂȯ

Try it online!

Explanation

Ṗʂȯ  # Implicit input
Ṗ    # Cartesian product
 ʂ   # Sum each
  ȯ  # Set intersection
     # Logical NOT
     # Implicit output
\$\endgroup\$
0
\$\begingroup\$

PowerShell 50 bytes

param($a)$a|%{$b=$_;$a|%{if($b+$_-in$a){1;break}}}

Where 1 is true and no output is false.

Though, if outputting multiple truthy values is allowed, then I could save 6 bytes:

param($a)$a|%{$b=$_;$a|%{if($b+$_-in$a){1}}}

But I will wordsmith myself and agree that the OP asked for 'a Truthy value'

Explanation:

param($a)$a|%{$b=$_;$a|%{if($b+$_-in$a){1;break}}}
param($a)                                          # assigns first passed parameter to variable $a
         $a|${                                   } # foreach $_ in $a
              $b=$_;                               # assign $_ to $b for access from further down the pipe
                    $a|%{                       }  # foreach $_ in $a
                         if($b+$_-in$a){       }   # if $a contains the value $b+$_
                                        1;         # implicit output of 1 (true)
                                          break    # exit the loops
\$\endgroup\$
0
0
\$\begingroup\$

Japt -!, 9 bytes

ø¡UË+XÃÃc

Try it online!

Unpacked & How it works

UøUmX{UmD{D+X} } c

Uø  Does the input array have any common element with...
UmX{  the input array mapped with...
UmD{    the input array mapped with...
D+X       sum of the two elements
}
}
c     ... flattened

The result is the opposite of what is requested, so -! flag is used to flip true and false.

\$\endgroup\$
1
  • \$\begingroup\$ 7 bytes: øUc@m+X \$\endgroup\$
    – Shaggy
    Oct 4, 2020 at 18:52
0
\$\begingroup\$

Cjam, 10 bytes

__m*::+&!!

Not very golfed. If someone can help me shave off more bytes, please help!

Explanation:

__         Duplicate the list twice
  m*       Take the Cartesian Product of the two
    ::+    For every item in the list (which is a list in this case), sum the elements
       &   Take the intersection with the original list
        !! Logical-not twice; take the "truthness" of the value
\$\endgroup\$
0
\$\begingroup\$

Japt -!, 4 bytes

øUï+

Try it here

\$\endgroup\$
0
\$\begingroup\$

Arturo, 37 bytes

$->a->¬some? a'x->some? a=>[in?+x&a]

Try it

\$\endgroup\$
0
\$\begingroup\$

[Matlab] 38 bytes

assuming a is the input array (in form of a=[1 3 5]

sum(sum(ismember(diff(perms(a)),a)))>0
\$\endgroup\$
0
\$\begingroup\$

Nekomata + -e, 5 bytes

ᵒ+j∕=

Attempt This Online!

ᵒ+       Addition table
  j      Flatten
   ∕     Set minus
    =    Check equality
\$\endgroup\$
0
\$\begingroup\$

JavaScript (V8), 41 bytes

f=(x,p,q)=>x.every(t=>1/q?p+q-t:f(x,t,p))

Try it online!

\$\endgroup\$
0
\$\begingroup\$

C (clang), 66 bytes

i;f(*a,n,*r){*r=1;for(i=n*n*n;i--;)*r&=a[i/n%n]+a[i%n]!=a[i/n/n];}

Try it online!

\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.