The $\Theta(n)$ difference-of-sums solution proposed by Tobi and Mario can in fact be generalized to any other data type for which we can define a (constant-time) binary operation $\oplus$ that is:
- total, such that for any values $a$ and $b$, $a \oplus b$ is defined and of the same type (or at least of some appropriate supertype of it, for which the operator $\oplus$ is still defined);
- associative, such that $a \oplus (b \oplus c) = (a \oplus b) \oplus c$;
- commutative, such that $a \oplus b = b \oplus a$; and
- cancellative, such that there exists an inverse operator $\ominus$ that satisfies $(a \oplus b) \ominus b = a$. Technically, this inverse operation doesn't even necessarily have to be constant-time, as long as "subtracting" two sums of $n$ elements each doesn't take more than ${\rm O}(n)$ time.
(If the type can only take a finite number of distinct values, these properties are sufficient to make it into an Abelian group; even if not, it will at least be a commutative cancellative semigroup.)
Using such an operation $\oplus$, we can define the "sum" of an array $a = (a_1, a_2, \dots, a_n)$ as $$(\oplus\, a) = a_1 \oplus a_2 \oplus \dotsb \oplus a_n.$$ Given another array $b = (b_1, b_2, \dots, b_n, b_{n+1})$ containing all the elements of $a$ plus one extra element $x$, we thus have $(\oplus\, b) = (\oplus\, a) \oplus x$, and so we can find this extra element by computing: $$x = (\oplus\, b) \ominus (\oplus\, a).$$
For example, if the values in the arrays are integers, then integer addition (or modular addition for finite-length integers types) can be used as the operator $\oplus$, with subtraction as the inverse operation $\ominus$. Alternatively, for any data type whose values can be represented as fixed-length bit strings, we can use bitwise XOR as both $\oplus$ and $\ominus$.
More generally, we can even apply the bitwise XOR method to strings of variable length, by padding them up to the same length as necessary, as long as we have some way to reversibly remove the padding at the end.
In some cases, this is trivial. For example, C-style null terminated byte strings implicitly encode their own length, so applying this method for them is trivial: when XORing two strings, pad the shorter one with null bytes to make their length match, and trim any extra trailing nulls from the final result. Note that the intermediate XOR-sum strings can contain null bytes, though, so you'll need to store their length explicitly (but you'll only need one or two of them at most).
More generally, one method that would work for arbitrary bit strings would be to apply one-bit padding, where each input bitstring is padded with a single $1$ bit and then with as many $0$ bits as necessary to match the (padded) length of the longest input string. (Of course, this padding does not need to be done explicitly in advance; we can just apply it as needed while computing the XOR sum.) At the end, we simply need to strip any trailing $0$ bits and the final $1$ bit from the result. Alternatively, if we knew that the strings were e.g. at most $2^{32}$ bytes long, we could encode the length of each string as a 32-bit integer and prepend it to the string. Or we could even encode arbitrary string lengths using some prefix code, and prepend those to the strings. Other possible encodings exist as well.
In fact, since any data type representable on a computer can, by definition, be represented as a finite-length bit string, this method yields a generic $\Theta(n)$ solution to the problem.
The only potentially tricky part is that, for the cancellation to work, we need to choose a unique canonical bitstring representation for each value, which could be difficult (indeed, potentially even computationally undecidable) if the input values in the two arrays may be given in different equivalent representations. This is not a specific weakness of this method, however; any other method of solving this problem can also be made to fail if the input is allowed to contain values whose equivalence is undecidable.
