Challenge 2: 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.
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: 9Explanation: 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) = bIn another example, a, b, and c are arbitrary constants, then:
2 * (a + b + c) − (a + a + b + b + c) = cJava
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.