Challenge 1: Single Number

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(n²)
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.