A few days ago, during a job interview, I was asked to live code three exercises in JavaScript:

- Palindrome check
- Find the element that appears once
- Fizz Buzz

Exercises 1 and 3 went pretty well. I was able to implement them correctly, even though, for Exercise 1, my initial answer didn't cover all the edge cases (forgot about space characters and upper/lower case).

Exercise 2 was a bit trickier for me.

Given an array of integers, all the elements appear twice, except one element that appears only once. Write an algorithm to find that element.

The most obvious, brute force solution, consists of two nested loops, where each
element in the array is compared with all the other elements, in order to find
which element is not repeated. **Time complexity** of this solution is O(n^2).

I wanted to avoid an answer with such time complexity - also didn't want to
write two nested `for`

loops. So, my first instinct was to look for a higher
order function, such as, `Array.prototype.find()`

or `Array.prototype.filter()`

,
to which I could pass a function that counted the number of occurrences of an
element in the array.

Since I was allowed to check the web for syntax and built-in methods, I started searching for such a method.

I realized there's no built-in method that does this in JavaScript and wasn't finding a simple and elegant solution.

As I decided to implement a working solution, and worry about optimization later, the interviewer rightfully commented about the time complexity of the algorithm I was writing.

In fact, this approach also has time complexity O(n^2).

The interviewer proceeded to suggest creating an object and using the array elements as its properties, to which the corresponding values would keep a counter on the number of occurrences.

I immediately remembered doing something similar before, so I knew
`Array.prototype.reduce()`

was the way to go.

As I started to implement, I took a bit too much time to figure up the function
I needed to pass to `reduce()`

and I didn't get the chance to
finish.

So, here I am to complete this challenge and improve my understanding on how
`reduce()`

operates ๐.

This solution has time complexity O(n) and consists of using a hash map to store
the count of each element. Then, it iterates through the keys and returns the
key which has count `1`

.

```
function findElementOnce(arr) {
let hash = arr.reduce((acc, value) => {
acc.hasOwnProperty(value) ? acc[value]++ : acc[value] = 1;
return acc;
}, {});
for (const key in hash) {
if (hash[key] === 1) {
return key;
}
}
}
```

Important notes about this solution, which became now, clearer to me:

- the use of method
`Object.prototype.hasOwnProperty()`

to check whether the object already has the specified element as property. - the function that's passed to
`reduce()`

has to return the accumulator. - the second parameter of
`reduce()`

, an empty object`{}`

, as the initial value that is assigned to the accumulator.

During my research for this article, I've discovered that this challenge can also be solved efficiently, with time complexity O(n), using the operator XOR.

In fact, it can even be considered more efficient, since in terms of **space
complexity** it has O(1), whilst the hashing solution has O(n).

```
function findElementOnce(arr) {
if(arr.length == 0) return;
let xor = arr[0];
for (let i = 1; i < arr.length ; i++) {
xor ^= arr[i];
}
return xor;
}
```

We know that `A XOR A = 0`

. If we XOR all the elements in the array, the
elements which are repeated twice will become `0`

, while the element which
is appearing only once will remain.

There's also a more complex version of this problem, where every element appears three times instead of twice, but I'll leave it for you to dive deeper ๐.