Solving a Code Wars Challenge with the Reduce Method and a Bitwise Operator

While solving problems on Code Wars, I came across an interesting problem called Find the Odd Int. It seemed simple at first, but one particular solution fascinated me so much that I decided to write about it.

The problem

Here's what the problem asks you to do:

For example:

• [1,1,2] → return 2

• [1,3,1,3,1] → return 1

The solution

My solution used an object to count the occurrences of each number, but I stumbled upon a more elegant solution other programmers came up with:

function findOdd(arr) {
    return arr.reduce((accumulator, currentValue) => accumulator ^ currentValue)
}

As a beginner, it took me some time to understand this concise function. Let's break it down.

The reduce() method

Let's break the function down into individual components, starting with the reduce() method.

The reduce() method can be called on an array. It executes a reducer callback function on each element of the array. The value the callback function returns is then passed into the callback function again on the next invocation as accumulator. After it processes all elements of the array, it returns a single value (the accumulated result). To understand the reduce() method better, let's use it to sum all the numbers in an array (which is a common use case of this method). Here's an example of how to do so:

const arr = [1, 2, 3, 4]

// (0) + 1 + 2 + 3 + 4
const sum = arr.reduce(
    (accumulator, currentValue) => accumulator + currentValue,
    0
)
// sum = 10

The reduce() method iterates over all numbers in the array. On each iteration, two variables (accumulator and currentValue) are passed to the callback function. The currentValue stores the current number of the array and the accumulator variable stores the accumulated result, which is then returned by the reduce() method after we iterate over all elements of the array. Because we have passed a 0 as the second argument to the reduce() method, the accumulator is initially set to 0.

If we don't specify the initial value, the array element at index 0 is used as the initial value and we start the iteration from the second element (at index 1). Here's the same example without the initial value:

const arr = [1, 2, 3, 4]

// 1 + 2 + 3 + 4
const sum = arr.reduce(
    (accumulator, currentValue) => accumulator + currentValue
)
// sum = 10

The XOR (^) operator

XOR (exclusive or) is a bitwise operator that returns 0 (false) if two bits are the same and 1 (true) if they are different. In JavaScript, the syntax for XOR is ^, while in mathematics, the ⊕ symbol is commonly used.

Let's look at an example. We will 'XOR' numbers 2 and 7.

console.log(2 ^ 7) // 5

The above code will print out 5, because if we write down the numbers in binary and perform the XOR operation on each pair of bits, we will get 101, which is 5 in decimal.

It's important to note, that if we use the XOR operator on two same numbers, the result is 0.

And if we use the XOR on any number \(x\) and 0, the result is \(x\). For example, if we "XOR" numbers 2 and 0, we get 2.

Another important property of the XOR operation is that it is associative and commutative. This simply means that the order of input values and how they're grouped doesn't affect the final output. For example, (1 ⊕ 2) ⊕ 3 gives us the same result as 2 ⊕ (1 ⊕ 3).

Putting things together

Let's put everything together and walk through the execution of the findOdd() function. We were given an array with these values: [1,2,1]. We will apply the reduce() method on this array. Because we don't pass in the initial value, the first element is used as the initial value (we will set the accumulator to 1) and start iterating from the second element.

During the first iteration, the accumulator is set to 1 and the currentValue is set to 2. The callback function returns 3 (1 ⊕ 2 or in binary 01 ⊕ 10).

In the next iteration, the accumulator is set to 3 and the currentValue is set to 1. The callback function returns 2 (3 ⊕ 1 or in binary 11 ⊕ 01).

Because there are no more elements in the array, the reduce() method returns the accumulated result, which in our case is 2.

If we put the syntax aside, all the findOdd() function does is 'XORing' all numbers in the given array and returning the result.

But how does 'XORing' all numbers give us the correct answer to our problem? Well, because we said that the order and grouping of the input values doesn't matter, we can rewrite it as:

'XORing' same numbers results in 0. This also applies to 'XORing' the same number an even number of times. Because of that, all numbers that occur an even number of times in our array will result in 0:

We are left with the number that occurs an odd number of times (and as the problem instructions state, such a number is only one in the array).

On the other hand, when we 'XOR' the same number \(x\) an odd number of times, the result is \(x\). Here is an example to showcase that:

So by 'XORing' all numbers of the array (using the reduce() method) and returning the result, we get the answer to our problem. This method works for all arrays that satisfy the problem's description - here are some more examples:

Summary

In this article, we discussed the reduce() method and the XOR operator, focusing on its key properties:

• x ⊕ x = 0

• x ⊕ 0 = x

• Associative and commutative properties allow rearranging and grouping without affecting the result.

We then applied these concepts to solve a programming problem. This solution is not only concise but also highlights the powerful and elegant use of bitwise operations in programming.

Sources🔗

• ⛩️ Kata

• 📄 Array.prototype.reduce() (mdn web docs)

• 📄 JS Bitwise Operations (W3School)

• 📄 XOR (StudySmarter)