> ## Content Index
> Fetch the complete content index at: https://www.javahandbook.com/llms.txt
> Use this file to discover other available public pages before exploring further.

# Challenge 1: Single Number
- URL: https://www.javahandbook.com/bitmask/challenge-1-single-number-2/
- Published: 2025-08-07T03:26:54.000Z
- Updated: 2025-08-07T03:26:54.000Z
- Description: In this lesson, every element appears twice except one element. We solve this using naive, and then we move to solve it more optimally using XOR operator.
- Author: Gopi Gorantala
- Tags: XOR Operator, #bitmask, #docs

In this lesson, every element appears twice except one element. Try to come up with a process to solve this. Use your XOR skills to achieve this.

## Introduction

In this question, every element appears twice except one element, which is our answer.

Let’s see how to achieve this using the **XOR** operator.

## Problem statement

We need to write a program that finds the element that is not repeated.

```json
Input: nums = { 4, 1, 2, 9, 1, 4, 2 } 

Output: 9
```

Explanation: Except for 9, all elements are repeated.

Assume `n` is non-negative.

**Hint:** Use the `^` operator to achieve this.

## Thought process

We solve this using naive, and then we move to solve it more optimally.

## Brute force approach

This is a naive approach. We traverse the entire array twice to achieve this, which is not optimal.

### Algorithm

Iterate the elements using two for-loops and find the one that is not repeating.

### Complexity analysis

Time Complexity: O(n2)  
Space Complexity: O(1).

## Hashtable approach

This approach is better than the one we did previously, as we are iterating over all the elements once with `*O*(*n*)` extra memory space.

### Algorithm

We use a hash table to avoid the `O(*n*)` time required for searching the elements.

Iterate through all elements in `nums` and set up a `key`/`value` pair.

Return the element that appeared only once.

### Java

```java
import java.util.HashMap;

class SingleNumber {
    private static int singleNumber(int[] nums) {
        HashMap<Integer, Integer> lookup = new HashMap<>();

        for (int i : nums) {
            lookup.put(i, lookup.getOrDefault(i, 0) + 1);
        }

        for (int i : nums) {
            if (lookup.get(i) == 1) {
                return i;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {4, 1, 2, 9, 1, 4, 2};
        System.out.println("Element appearing one time is " + singleNumber(nums));
    }
}
```

### Python

```py
from collections import defaultdict

def singleNumber(nums):
    lookup = defaultdict(int)

    for i in nums:
        lookup[i] += 1

    for i in nums:
        if lookup[i] == 1:
            return i

    return -1

nums = [4, 1, 2, 9, 1, 4, 2]
print("Element appearing one time is", singleNumber(nums))

```

### JavaScript

```js
const SingleNumber = array => {

    function helper (nums) {
        const lookup = {};

        for(let el of nums) {
            lookup[el] = lookup[el] ? ++lookup[el] : 1;
        }

        for(let value of nums) {
            if(lookup[value] === 1) {
                return value;
            }
        }

        return -1;
    }

    return helper (array);
}

const array = [4, 1, 2, 9, 1, 4, 2];
console.log (`Element appearing one time is ${SingleNumber (array)}`);

```

### C++

```cpp
#include <iostream>
#include <map>

void SingleElement(int *arr, int n) {
    std::map<int, int> my_map;
    std::map<int, int>::iterator it;
    for (int i = 0; i < n; i++) {
        my_map[arr[i]]++;
    }
    for (it = my_map.begin(); it != my_map.end(); it++) {
        if (it->second == 1) {
            std::cout << "Element appearing one time is " << it->first << std::endl;
            return;
        }
    }
}

int main() {
    int arr[] = {4, 1, 2, 9, 1, 4, 2};
    SingleElement(arr, sizeof(arr) / sizeof(arr[0]));
    return 0;
}
```

### TypeScript

```ts
export const SingleNumber = (array: number[]): number => {
    function helper(nums: number[]): number {
        const lookup: object = {};

        for (let el of nums) {
            lookup[el] = lookup[el] ? ++lookup[el] : 1;
        }

        for (let value of nums) {
            if (lookup[value] === 1) {
                return value;
            }
        }

        return -1;
    }

    return helper(array);
}

const array: number[] = [4, 1, 2, 9, 1, 4, 2];
console.log(`Element appearing one time is ${SingleNumber(array)}`);

```

### Complexity analysis

**Time complexity:** `*O*(*n*)`. The time complexity of the for loop is `*O*(*n*)`. The time complexity of the hash table operation pop is `*O*(1)`.

**Space complexity:** `*O*(*n*)`. The space required by `hash_table` is equal to the number of elements in `nums`.

## Math approach

### Algorithm

Let’s consider some arbitrary constants and write some formulae.

Consider `a` and `b` arbitrary constants, then:

> `2 * (a + b) − (a + a + b) = b`

In another example, `a`, `b`, and `c` are arbitrary constants, then:

> `2 * (a + b + c) − (a + a + b + b + c) = c`

### Java

```java
import java.util.HashSet;

class SingleNumber {
    private static int singleNumber(int[] nums) {
        int sumOfUniqueElements = 0, totalSum = 0;
        HashSet<Integer> set = new HashSet<>();

        for (int num : nums) {
            if (!set.contains(num)) {
                set.add(num);
                sumOfUniqueElements += num;
            }
            totalSum += num;
        }
        return 2 * sumOfUniqueElements - totalSum;
    }

    public static void main(String[] args) {
        int[] nums = {4, 1, 2, 9, 1, 4, 2};
        System.out.println("Element appearing one time is " + singleNumber(nums));
    }
}
```

### Python

```py
def singleNumber(nums):
    sum_of_unique_elements = 0
    total_sum = 0
    num_set = set()

    for num in nums:
        if num not in num_set:
            num_set.add(num)
            sum_of_unique_elements += num
        total_sum += num

    return 2 * sum_of_unique_elements - total_sum

nums = [4, 1, 2, 9, 1, 4, 2]
print("Element appearing one time is", singleNumber(nums))

```

### JavaScript

```js
const SingleNumber = array => {

    function helper (nums) {
        let sumOfUniqueElements = 0;
        let totalSum = 0;

        //The Set object lets you store unique values of any type, whether primitive values or object references.
        const lookup = new Set ();

        for(let el of nums) {
            if(!lookup.has (el)) {
                lookup.add (el);
                sumOfUniqueElements += el;
            }
            totalSum += el;
        }
        return (2 * sumOfUniqueElements) - totalSum;
    }

    return helper (array);
}

const array = [4, 1, 2, 9, 1, 4, 2];
console.log (`Element appearing one time is ${SingleNumber (array)}`);

```

### C++

```cpp
#include <map>
#include <iostream>

using namespace std;

int singleNumber(int nums[], int n) {
    map<int, int> m;
    long sum1 = 0, sum2 = 0;

    for (int i = 0; i < n; i++) {
        if (m[nums[i]] == 0) {
            sum1 += nums[i];
            m[nums[i]]++;
        }
        sum2 += nums[i];
    }
    return 2 * (sum1) - sum2;
}

int main() {
    int a[] = {4, 1, 2, 9, 1, 4, 2};
    int n = 7;
    cout << "Element appearing one time is " << singleNumber(a, n) << "\n";
    return 0;
}
```

### TypeScript

```ts
export const SingleNumber = (array: number[]): number => {
    function helper(nums: number[]): number {
        let sumOfUniqueElements: number = 0;
        let totalSum: number = 0;

        //The Set object lets you store unique values of any type, whether primitive values or object references.
        const lookup = new Set();

        for (let el of nums) {
            if (!lookup.has(el)) {
                lookup.add(el);
                sumOfUniqueElements += el;
            }
            totalSum += el;
        }
        return (2 * sumOfUniqueElements) - totalSum;
    }

    return helper(array);
}

const array: number[] = [4, 1, 2, 9, 1, 4, 2];
console.log(`Element appearing one time is ${SingleNumber(array)}`);

```

### Complexity analysis

**Time complexity:** `*O*(*n*)`. The time complexity of the for loop is `*O*(*n*)`.

**Space complexity:** `*O*(*n*)`. The space required by hash\_table is equal to the number of elements in `nums`.

## Coding exercise

First, look at these code snippets above and think of a solution.

Your solution must use the `^` operator.

This problem is designed for your practice, so try to solve it yourself first. If you get stuck, you can always refer to the solution section's solution. Good luck!

```java
// java
// TODO: finish the challenge or check next lesson for solution
class Solution {
    public static int singleNumber(int[] nums) {
       // Write - Your - Code- Here
        
        return -1; // change this, return element appearing one time over the array of elements, if none, return -1
    }
}
```

```py
# Python
# TODO: finish the challenge or check next lesson for solution
def singelNumber(nums):
	# Write - Your - Code- Here
    
    return -1 # change this, return element appearing one time over the array of elements, if none, return -1
```

```js
// javascript
// TODO: finish the challenge or check next lesson for solution
const SingleNumber = nums => {
  // Write - Your - Code- Here
        
  return -1; // change this, return element appearing one time over the array of elements, if none, return -1
}
```

```cpp
// c++
// TODO: finish the challenge or check next lesson for solution
#include <iostream>
using namespace std;

int singleNumber(int n) {
  // Write - Your - Code- Here
        
  return -1; // change this, return element appearing one time over the array of elements, if none, return -1
}
```

```ts
// typescript
// TODO: finish the challenge or check next lesson for solution
export const SingleNumber = (nums: number[]): number => {
  // Write - Your - Code- Here
        
  return -1; // change this, return element appearing one time over the array of elements, if none, return -1
}
```

The solution will be explained in the next lesson.