Skip to content

# Challenge 1: Single Number

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.

## Table of Contents

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.

``````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

``````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

``````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

``````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++

``````#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

``````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

``````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

``````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

``````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++

``````#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

``````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
// 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
}
}``````
``````# 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``````
``````// 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
}``````
``````// 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
}``````
``````// 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.

Coding Interview QuestionsData Structures and AlgorithmsArraysBit Manipulation

### Gopi Gorantala Twitter

Gopi is an engineering leader with 12+ of experience in full-stack development—a specialist in Java technology stack. He worked for multiple startups, the European govt, and FAANG in India and Europe.

Members Public

## Leetcode 217: Contains Duplicate

This question marks the first problem when working on duplicate data, either integers or strings etc. Companies that have asked this in their coding interview are Amazon, Apple, Netflix, Google, Microsoft, Adobe, Facebook, and many more top tech companies. Problem statement Given an integer array nums, return true if any

Members Public

## Leetcode 121: Best Time To Buy and Sell Stock

The Best time to buy and sell stock problem is a classic problem that can be solved using the Greedy approach. This is one of the most popular questions asked in such interviews. Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe,

Members Public

## Arrays From Zero To Mastery: A Complete Notes For Programmers

This article discusses array data structure with sketches, memory diagrams, array capacity vs. length, strengths & weaknesses, big-O complexities, and more!