Day 0 - Given a non-empty array of integers, every element appears twice except for one. Find that single one.

As a part of LeetCode's 30 Days 30 Challenges.

Problem Statement

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1 -

Input: [2,2,1]
Output: 1

Input: [4,1,2,1,2]
Output: 4

Possible Approaches for solving the given problem

Approach 1

Iterate over the given array. Add the element in the dictionary. Keep a check if the key already exists in the dictionary. Keep count of the element as the value. Then return the element(key) whose value(count) is 1.

Problem with this approach

It'll iterate the complete list.
Once the dictionary gets created. To return the element with count 1 again value corresponding to every element will have to be checked.
Making the time complexity - O(n^2)
This would also lead to runtime error.

Approach 2

As the elements in the list are repeated. Convert the list into a set. A set consists of only unique elements.
Instead of iterating over a complete list which would be complexity O(n). Iterate over the set i.e unique elements only.
Iterate over the set and check the count of that element in the list. If count is 1. Return the element.

Reasons this is better approach

We are not iterating over the complete array of duplicate elements unnecessarily hence making the solution efficient.
Time Complexity - O(n). The complexity of the earlier solution was O(n^2).

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        unique_nums = set(nums)
        for element in unique_nums:
            count = nums.count(element)
            if count == 1:
               return element

Learnings