DEV Community

loading...

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

mridubhatnagar profile image Mridu Bhatnagar ・2 min read

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

  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

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

Approach 2

  1. As the elements in the list are repeated. Convert the list into a set. A set consists of only unique elements.
  2. Instead of iterating over a complete list which would be complexity O(n). Iterate over the set i.e unique elements only.
  3. 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

  1. We are not iterating over the complete array of duplicate elements unnecessarily hence making the solution efficient.
  2. 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

  1. Time complexity of set is O(1).
  2. Time complexity of list count is 0(n).
  3. Set consists of unique elements.

Reference Links
https://leetcode.com/explore/other/card/30-day-leetcoding-challenge/528/week-1/3283/

Discussion

pic
Editor guide
Collapse
shanecandoit profile image
outOfBounds

You could also xor all the digits. The second occurrence cancels out the first.

No extra memory beyond a single int used.