14
\$\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!

Improve this question
\$\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\$
    – Unrelated String
    Jun 22, 2021 at 9:43
  • 1
    \$\begingroup\$ ...also, there seem to be two missing elements in the last test case (23 and 9). \$\endgroup\$
    – Unrelated String
    Jun 22, 2021 at 9:46
  • 1
    \$\begingroup\$ @UnrelatedString Oops, typing by hand. \$\endgroup\$
    – emanresu A
    Jun 22, 2021 at 9:47

24 Answers 24

Reset to default
21
\$\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.

Improve this answer
\$\endgroup\$
11
\$\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.

Improve this answer
\$\endgroup\$
5
  • 1
    \$\begingroup\$ I'm pretty sure your 25-byte version is valid. \$\endgroup\$
    – Arnauld
    Jun 22, 2021 at 10:35
  • \$\begingroup\$ Yes, the 25-byter is valid. \$\endgroup\$
    – emanresu A
    Jun 22, 2021 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, 2021 at 6:35
  • \$\begingroup\$ @FZs you can find out code using ...a in post's history version \$\endgroup\$
    – tsh
    Jun 23, 2021 at 6:46
  • \$\begingroup\$ @tsh Oh, I see: you started from the same thing. Anyway, you've had it earlier... \$\endgroup\$
    – FZs
    Jun 23, 2021 at 6:48
7
\$\begingroup\$

Jelly, 2 bytes

œ-

Try it online!

Just the set difference builtin

Improve this answer
\$\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.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Annoying that setdiff can't handle multiple identical elements, or it could do the job for 7... \$\endgroup\$
    – Dominic van Essen
    Jun 22, 2021 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
Improve this answer
\$\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!

Improve this answer
\$\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
Improve this answer
\$\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.

Improve this answer
\$\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, 2021 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, 2021 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, 2021 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.

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

Brachylog, 3 bytes

+ᵐ-

Try it online!

Improve this answer
\$\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

Improve this answer
\$\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, 2021 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.

Improve this 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, 2021 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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Julia, 15 bytes

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

Try it online!

similar to dingledooper's answer

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

J, 5 bytes

XOR@,

Try it online!

A port of tsh's clever answer.

Improve this 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
Improve this answer
\$\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

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Java (JDK), 21 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Factor + math.unicode, 16 bytes

[ [ Σ ] bi@ - ]

Try it online!

Improve this answer
\$\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.

Improve this answer
\$\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.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 11 bytes

Tr@#-Tr@#2&

Try it online!

Used algorithm from dingledooper's answer

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Perl 5, 35 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

J-uby, 11 bytes

:*&:sum|+:-

Attempt This Online!

Explanation

:* & :sum | +:-

:* & :sum |      # Map with .sum, then
            +:-  # difference
Improve this answer
\$\endgroup\$

Your Answer

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

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