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

36 Answers 36

1
2
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 '20 at 19:11
  • \$\begingroup\$ @Zgarb added it in.. \$\endgroup\$ – Razetime Oct 7 '20 at 12:18
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 '20 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\$

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\$
0
\$\begingroup\$

Japt -!, 4 bytes

øUï+

Try it here

\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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