15
\$\begingroup\$

Write a program which takes two arrays of positive integers as input. One of them (your choice which) will have one item missing compared to the other. Your program must figure out what is missing.

Rules

You can choose which array has one missing: You can take ordinary then missing or vice versa.

Arrays may contain duplicates.

Testcases

[1,2,3], [1,3] => 2
[3,3,3,3,3], [3,3,3,3] => 3
[4,6,1,6,3,5,2], [3,6,2,5,4,6] => 1
[9,9,10,645,134,23,65,23,45,12,43], [43,134,23,65,12,9,10,645,45,9] => 23

This is , shortest bytes wins!

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Probably worth changing the title to reflect that this is really a multiset difference problem, seeing as items have multiplicities \$\endgroup\$ Jun 22 at 9:43
  • 1
    \$\begingroup\$ ...also, there seem to be two missing elements in the last test case (23 and 9). \$\endgroup\$ Jun 22 at 9:46
  • 1
    \$\begingroup\$ @UnrelatedString Oops, typing by hand. \$\endgroup\$
    – emanresu A
    Jun 22 at 9:47

23 Answers 23

20
\$\begingroup\$

Python 2, 24 bytes

Takes two lists \$ a \$ and \$ b \$, where \$ b \$ has the missing number.

lambda a,b:sum(a)-sum(b)

Try it online!

Given that \$ a \$ and \$ b \$ differ by a single number, we can trivially obtain the answer by computing the difference of sums.

\$\endgroup\$
9
\$\begingroup\$

JavaScript (ES2019), 25 bytes

a=>eval(a.flat().join`^`)

Try it online!

Take input as f([array1, array2]).

Calculate xor of all input numbers.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ I'm pretty sure your 25-byte version is valid. \$\endgroup\$
    – Arnauld
    Jun 22 at 10:35
  • \$\begingroup\$ Yes, the 25-byter is valid. \$\endgroup\$
    – emanresu A
    Jun 22 at 10:44
  • \$\begingroup\$ I was going to come up with the same thing (just with taking ...a as argument, not realizing it's possible to take an array of arrays), but before submitting, I found yours. Have a vote ;) \$\endgroup\$
    – FZs
    Jun 23 at 6:35
  • \$\begingroup\$ @FZs you can find out code using ...a in post's history version \$\endgroup\$
    – tsh
    Jun 23 at 6:46
  • \$\begingroup\$ @tsh Oh, I see: you started from the same thing. Anyway, you've had it earlier... \$\endgroup\$
    – FZs
    Jun 23 at 6:48
7
\$\begingroup\$

Jelly, 2 bytes

œ-

Try it online!

Just the set difference builtin

\$\endgroup\$
2
5
\$\begingroup\$

R, 19 bytes

sum(scan(),-scan())

Try it online!

Same idea as dingledooper's Python answer, using R's terser syntax for sum. Input is taken from STDIN, with the two multisets separated by a newline.

\$\endgroup\$
1
  • \$\begingroup\$ Annoying that setdiff can't handle multiple identical elements, or it could do the job for 7... \$\endgroup\$ Jun 22 at 10:58
4
\$\begingroup\$

Haskell, 12 bytes

foldl(-).sum

Try it online!

A cooler way to write (\x y->sum x-sum y). For example,

    (foldl(-).sum) [4,6,1,6,3,5,2] [3,6,2,5,4,6]
=== (foldl (-) (sum [4,6,1,6,3,5,2])) [3,6,2,5,4,6]
=== (4+6+1+6+3+5+2)-3-6-2-5-4-6
=== 1
\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES6), 43 bytes

Expects (a)(b), where b has one item missing. Returns a singleton.

This one is a bit overkill and would work with several missing items.

a=>b=>b.map(v=>a.splice(a.indexOf(v),1))&&a

Try it online!


JavaScript (ES6), 35 bytes

Using dingledooper's sum trick. Same input format. Returns an integer.

a=>b=>eval(a.join`+`+'-'+b.join`-`)

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Vyxal, 3 bytes

v∑¯

Try it Online!

Very epic port of the python answer. Takes original and missing in a list.

Explained

v∑¯
v∑  # sum of each list
  ¯ # and deltas
\$\endgroup\$
3
\$\begingroup\$

C (gcc), 50 \$\cdots\$ 44 43 bytes

Saved 5 6 bytes thanks to an idea from AZTECCO!!!

c;f(a,b)int*a,*b;{c=*a?f(a+1,b+1)^*a^*b:0;}

Try it online!

Inputs \$2\$ zero-terminated arrays (since pointers to arrays in C carry no length information) of positive integers with the \$2^{\text{nd}}\$ array the same as the \$1^{\text{st}}\$ except for a missing number.
Returns the missing number.

Explanation

Since exclusive-or (\$\oplus\$) is associative and commutative, \$n\oplus n=0\$, and \$n\oplus 0=n\$ we can simply exclusive-or all the numbers from both arrays together to yield the missing number. This is also guaranteed to always fit inside an int as no extra bits are ever needed.

\$\endgroup\$
3
  • \$\begingroup\$ The sum method lets you save 7 c;f(a,b)int*a,*b;{c=*a?f(a+1,b+1)+*a-*b:0;} \$\endgroup\$
    – AZTECCO
    Jun 22 at 15:19
  • \$\begingroup\$ @AZTECCO Think that's -6 bytes. Very clever using the \$0\$ from the end of b! Using that idea with xor to prevent overflow - thanks! :D \$\endgroup\$
    – Noodle9
    Jun 22 at 15:41
  • \$\begingroup\$ I was just pointing out that! I used *a? Instead of b that's why it works ;) \$\endgroup\$
    – AZTECCO
    Jun 22 at 15:46
3
\$\begingroup\$

Red, 34 bytes

func[a b][foreach u b[alter a u]a]

Try it online!

sum - sum.

-4 from dingledooper using the xor trick from tsh.

-15 bytes from Galen Ivanov using his alter tip.

Red, 71 63 bytes

func[a b][remove-each v a[c: NONE <> find b v replace b v""c]a]

Try it online!

Summing is shorter, but really, I just wanted to try using remove-each.

Returns a series with a single value (the differing element). Works as a general multiset difference as well.

\$\endgroup\$
3
  • \$\begingroup\$ 49 bytes with the "xor" trick. \$\endgroup\$ Jun 22 at 22:56
  • \$\begingroup\$ If the result can be returned as an array, here's a 34 bytes soluion \$\endgroup\$ Jun 23 at 8:00
  • \$\begingroup\$ Another cool thing about using alter here is that the order of arguments doesn't matter \$\endgroup\$ Jun 23 at 14:00
2
\$\begingroup\$

Brachylog, 3 bytes

+ᵐ-

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Ruby, 18 bytes

->a,b{a.sum-b.sum}

Try it online!


Ruby, 15 bytes

->*a{eval a*?^}

Try it online!

Based on tsh's Javascript solution.

Thanks to @G B for -3 on the 15 byte solution

\$\endgroup\$
1
  • \$\begingroup\$ Your 14-bytes solution is valid (but 1 byte longer) if you use the splat operator on its arguments: ->*a{...} \$\endgroup\$
    – G B
    Jun 22 at 11:09
2
\$\begingroup\$

Japt, 5 bytes

x)-Vx

x : Sums all elements in the array

Try it online!

Same idea as dingledooper's answer.

\$\endgroup\$
1
  • \$\begingroup\$ Welcome to PPCG and welcome to Japt :) For future reference, 'cause it might trip you up on another challenge, a space would suffice in place of the ). \$\endgroup\$
    – Shaggy
    Jun 22 at 15:32
2
\$\begingroup\$

Retina 0.8.2, 22 bytes

S`,
O`
+`^(.+¶)\1

1G`

Try it online! Takes arrays on separate lines but link is to test suite that splits on semicolons for convenience. Works on strings (if they don't contain commas or newlines) as well as integers. Explanation:

S`,

Split each array into separate strings.

O`

Sort both arrays.

+`^(.+¶)\1

Remove leading duplicates.

1G`

Remove trailing (assumed) duplicates.

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

J, 5 bytes

XOR@,

Try it online!

A port of tsh's clever answer.

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

yuno, 4 bytes

ΣϾ_/

Try it online!

Port of the Python solution. I don't have multiset difference built-in yet.

ΣϾ_/   ᴋ   Main Link
 Ͼ     ᴋ   For each list
Σ      ᴋ   Take its sum
   /   ᴋ   Then reduce over
  _    ᴋ   Subtraction
\$\endgroup\$
1
\$\begingroup\$

Japt, 5 bytes

Unfortunately, all of Japt's methods for getting the differences between 2 arrays don't take duplicates into account so we have to go with a longer method.

Takes input as a 2D-array, in either order.

mx ra

Try it

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

Julia, 15 bytes

a\b=sum([a;-b])

Try it online!

similar to dingledooper's answer

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

Factor + math.unicode, 16 bytes

[ [ Σ ] bi@ - ]

Try it online!

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

MATLAB/Octave, 17 bytes

@(a,b)sum([a,-b])

Try it online!
Like most of answers here makes use of difference of sums.
MATLAB got its own builtin setdiff but for one it doesn't work with multisets just regular sets and for second it's 1 byte longer.

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

Japt, 4 bytes

Takes input as an array containing two sub-arrays.

c r^
c    // Flatten, then
  r^ // reduce with XOR.

Try it here.

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

Wolfram Language (Mathematica), 11 bytes

Tr@#-Tr@#2&

Try it online!

Used algorithm from dingledooper's answer

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

Java (JDK), 21 bytes

a->b->a.sum()-b.sum()

Try it online!

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

Perl 5, 35 bytes

$_=pop@F;for$f(@F){s/,$f\b|\b$f,//}

Try it online!

\$\endgroup\$

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.