= Solution
Validate the complete input before doing the addition. The <arrays> use most-significant-digit-first <positional notation>. The result has one extra leading position, which contains either zero or the final carry.
``
def binaryAddition(x: Array[Int], y: Array[Int]): Array[Int] = {
require(x != null && y != null, "arrays must not be null")
require(x.length == y.length, "lengths must match")
val n = x.length
var k = 0
while (k < n) {
require((x(k) == 0 || x(k) == 1) &&
(y(k) == 0 || y(k) == 1), "digits must be 0 or 1")
k += 1
}
val answer = new Array[Int](n + 1)
var carry = 0
var j = n - 1
while (j >= 0) {
val column = x(j) + y(j) + carry
answer(j + 1) = column % 2
carry = column / 2
j -= 1
}
answer(0) = carry
answer
}
``
A failed `require` throws `IllegalArgumentException`, covering mismatched lengths, invalid <binary digits> and null <arrays>. The largest column sum is three, so the carry always lies in $\{0,1\}$. The <binary-addition carry invariant> says that the already processed input suffixes equal the written result suffix plus the carry shifted to the next column. After the final column, placing that carry at position zero proves the returned value is the sum. Neither input <array> is modified. Equal empty inputs are accepted as zero and return `Array(0)`; the specification imposes no positive-length restriction. <Running time> and result storage are $O(N)$.
Back to article page
