# HackerRank Lonely Integer solution with JavaScript

Let's learn how to solve the Lonely Integer challenge from the HackerRank website.

Given an array of integers, where all elements but one occur twice, we must find the lonely element that occurs only once.

## Example

```
a = [1, 2, 3, 4, 3, 2, 1];
```

In this example, the lonely integer is `4`

.

## Pseudo code solution

- Define a
`unique`

array to process the elements in the input array. - Sort the input array in ascending order so that duplicate values are beside each other.
- Loop over the input array.
- If the
`unique`

array does not contain the current array element, add it. - If the
`unique`

array does contain the current array element, remove it.

- If the
- Return the first index of the
`unique`

array, which is the lonely integer.

## Code solution

```
function lonelyinteger(a) {
let unique = [];
a.sort().forEach((item) => {
const hasItem = unique.includes(item);
if (!hasItem) {
unique.push(item);
} else {
unique.pop(item);
}
});
return unique[0];
}
```

If we want to avoid sorting the input array, we can use a JavaScript `Set`

instead.

```
function lonelyinteger(a) {
const set = new Set();
a.forEach((item) => {
if (set.has(item)) {
set.delete(item);
} else {
set.add(item);
}
});
return set.values().next().value; // or [...set][0]
}
```

## Test cases

```
console.log(lonelyinteger([0, 0, 1, 2, 1]));
```

The lonely integer for this array should be `2`

. The result is indeed what we expected.

```
console.log(lonelyinteger([1, 2, 3, 4, 3, 2, 1]));
```

The lonely integer for this array should be `4`

. The result is indeed what we expected.

## Time and space complexity

The Big O time complexity of the solution is comprised of the following.

`O(n log n)`

for the sorting with the JavaScript`sort`

method.`O(n)`

for iterating over the input array, where`n`

is the length of the input array.

When adding both together, we get a time complexity of `O(2n log n)`

, which is essentially just `O(n log n)`

, or logarithmic time complexity.

The Big O space complexity of the solution is constant, or `O(m)`

, where `m`

is the number of unique values from the input array. Even if we delete any duplicate value after detecting that it has already been stored, it still had to be stored. In the case of the `[0, 0, 1, 2, 1]`

input array, `[0, 1, 2]`

were stored in the `unique`

array, or the `set`

.