Mod 2 Multinomial coefficients

Question

quintopia has posted here a challenge to compute multinomial coefficients (some of the text here is copied from there). There is a fun algorithm to compute multinomial coefficients mod 2.

Given a list of numbers, k₁, k₂, ... ,k_m, output the residue of the multinomial coefficient:

reduced mod 2. The following algorithm does this efficiently: for each k_i, compute the binary expansion of k_i, that is, find a_ij such that each a_ij is either 1 or 0 and

If there is any j such that a_rj = a_sj = 1 for r ≠ s, then the associated mod 2 multinomial coefficient is 0, otherwise the mod 2 multinomial coefficient is 1.

Task

Write a program or function which takes m numbers, k₁, k₂, ... ,k_m, and outputs or returns the corresponding multinomial coefficient. Your program may optionally take m as an additional argument if need be.

• These numbers may be input in any format one likes, for instance grouped into lists or encoded in unary, or anything else, as long as the actual computation of the multinomial coefficient is performed by your code, and not the encoding process.

• Output can be any truthy value if the multinomial coefficient is odd and any falsey value if the multinomial coefficient is even.

• Built-ins designed to compute the multinomial coefficient are not allowed.

• Standard loopholes apply.

Scoring

This is code golf: Shortest solution in bytes wins.

Examples:

To find the multinomial coefficient of 7, 16, and 1000, we binary expand each of them:

Since no column has more than one 1, the multinomial coefficient is odd, and hence we should output something truthy.

To find the multinomial coefficient of 7, 16, and 76, we binary expand each of them:

Since both 76 and 7 have a 4 in their binary expansion, the multinomial coefficient is even and so we output a falsey value.

Test cases:

Input: [2, 0, 1]
Output: Truthy

Input: [5,4,3,2,1]
Output: Falsey

Input: [1,2,4,8,16]
Output: Truthy

Input: [7,16,76]
Output: Falsey

Input: [7,16,1000]
Output: Truthy

Input: [545, 1044, 266, 2240]
Output: Truthy

Input: [1282, 2068, 137, 584]
Output: Falsey

Input: [274728976, 546308480, 67272744, 135004166, 16790592, 33636865]
Output: Truthy

Input: [134285315, 33849872, 553780288, 544928, 4202764, 345243648]
Output: Falsey

Answer 1

Jelly, 4 bytes

S=|/

Try it online!

Test whether the sum is equal to the bitwise-or-sum (i.e. a+b+c == a|b|c).

Answer 2

Python 3 2, 55 43 42 bytes

lambda l:sum(l)==eval(`l`.replace(*',|'))

-12 bytes from Mr. Xcoder

-1 byte from Rod

Try it online!

Explanation: Checks if the sum of the numbers is equal to the bitwise-or of the numbers.

Answer 3

Python 2, 37 bytes

lambda l:sum(l)==reduce(int.__or__,l)

Try it online!

Another port of pizzapants184's algorithm...

Answer 4

Clean, 38 bytes

import StdEnv
?l=sum l==foldr(bitor)0l

Try it online!

Yet another port.

Answer 5

JavaScript (ES6), 37 35 34 bytes

Saved 2 bytes thanks to @Mr.Xcoder
Saved 1 byte thanks to @ETHproductions

Comparing the sum with the bitwise OR (like pizzapants184 and Leaky Nun did) is 1 3 4 bytes shorter than my initial approach:

a=>(q=c=>eval(a.join(c)))`|`==q`+`

Test cases

let f =

a=>(q=c=>eval(a.join(c)))`|`==q`+`

console.log(f([2, 0, 1]))                                                       // Truthy
console.log(f([5,4,3,2,1]))                                                     // Falsey
console.log(f([1,2,4,8,16]))                                                    // Truthy
console.log(f([7,16,76]))                                                       // Falsey
console.log(f([7,16,1000]))                                                     // Truthy
console.log(f([545, 1044, 266, 2240]))                                          // Truthy
console.log(f([1282, 2068, 137, 584]))                                          // Falsey
console.log(f([274728976, 546308480, 67272744, 135004166, 16790592, 33636865])) // Truthy
console.log(f([134285315, 33849872, 553780288, 544928, 4202764, 345243648]))    // Falsey

---

Alt. version, 38 bytes

a=>!a.some((x,i)=>a.some(y=>i--&&x&y))

Test cases

let f =

a=>!a.some((x,i)=>a.some(y=>i--&&x&y))

console.log(f([2, 0, 1]))                                                       // Truthy
console.log(f([5,4,3,2,1]))                                                     // Falsey
console.log(f([1,2,4,8,16]))                                                    // Truthy
console.log(f([7,16,76]))                                                       // Falsey
console.log(f([7,16,1000]))                                                     // Truthy
console.log(f([545, 1044, 266, 2240]))                                          // Truthy
console.log(f([1282, 2068, 137, 584]))                                          // Falsey
console.log(f([274728976, 546308480, 67272744, 135004166, 16790592, 33636865])) // Truthy
console.log(f([134285315, 33849872, 553780288, 544928, 4202764, 345243648]))    // Falsey

Answer 6

Japt, 6 bytes

Another port of pizzapants184's & Leaky Nun's solutions.

x ¶Ur|

Test it

Answer 7

Java 8, 53 bytes

a->{int i=0,j=0;for(int x:a){i+=x;j|=x;}return i==j;}

Port of @LeakyNun's Jelly answer.

Explanation:

Try it here.

a->{             // Method with integer-array parameter and boolean return-type
  int i=0,j=0;   //  Two integers, both starting at 0
  for(int x:a){  //  Loop over the array
    i+=x;        //   Add them to the first integer
    j|=x;}       //   And bitwise-OR it with the second integer
  return i==j;}  //  Return if both integers are the same after the loop

Answer 8

Haskell, 38 bytes

(==).sum<*>foldl1 xor is an anonymous function returning a Bool. Use as ((==).sum<*>foldl1 xor) [2,0,1].

import Data.Bits
(==).sum<*>foldl1 xor

Try it online!

• Pretty much the same trick by pizzapants184 and Leaky Nun that everyone uses, except that with Haskell operator names it saves one byte to use (bitwise) xor instead of (.|.) (bitwise or).

• (==).sum<*>foldl1 xor is a point-free version of \l->sum l==foldl1 xor l.

Answer 9

Pyth, 6 bytes

qsQ.|F

Test Suite.

Answer 10

Husk, 5 bytes

§=ΣFv

Try it online!

Answer 11

Perl 6, 15 bytes

{.sum==[+|] $_}

Test it

Expanded:

{  # bare block lambda with implicit parameter ｢$_｣

    .sum  # the sum of ｢$_｣ (implicit method call)

  ==

    [+|]  # reduce using &infix:«+|» (numeric binary or)

      $_  # the input
}

Answer 12

Red, 78 bytes

f: func[x][b: :to-binary t: 0 s: b 0 foreach n x[t: t + n s: s or b n]s = b t]

How it works:

Ungolfed:

Red []
f: func [x][         -  a function taking a block as an argument
    b: :to-binary    -  an alias for the to-binary function
    t: 0             -  set the sum of the numbers to 0
    s: b 0           -  set the "or" total to binary 0
    foreach n x[     -  for each number in the block
        t: t + n     -  add it to the sum
        s: s or b n  -  bitwise or of its binary representation with the total
    ]
    s = b t          - are the sum (binary) and the "or" total equal?
]

Try it online!

Answer 13

Wolfram Language (Mathematica), 15 bytes

Tr@#==BitOr@@#&

Try it online!

Answer 14

Batch, 73 bytes

@set/as=o=0
@for %%i in (%*)do @set/as+=%%i,o^|=%%i
@if %s%==%o% echo 1

Outputs 1 for truthy, nothing for falsy. Another obvious port of pizzapants184/Leaky Nun's algorithm.

Answer 15

J, 10 bytes

+/=+./&.#:

Yet another port of pizzapants184's & Leaky Nun's solutions.

How it works?

+/.&.#: - convert the numbers to binary, apply bitwise or to the powers of two and convert back from binary to decimal

+/ - reduce the input by addition

= - are the above equal?

Try it online!

Straightforward alternative

J, 12 bytes

2>[:>./+/@#:

How it works?

+/@#: - convert each number to binary and find the sum of each power of 2

>./ - find the maximum

2> - is it less than 2? -> truthy

Try it online!

Answer 16

Triangularity, 31 bytes

...)...
..IEu..
.)IE...
"|"JE=.

Try it online!

Alternate solution, 31 bytes

...)...
..IED..
.us"|".
JE=....

Try it online!