DEV Community

Mridu Bhatnagar
Mridu Bhatnagar

Posted on

4 1

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

  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/

Heroku

Build apps, not infrastructure.

Dealing with servers, hardware, and infrastructure can take up your valuable time. Discover the benefits of Heroku, the PaaS of choice for developers since 2007.

Visit Site

Top comments (1)

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.

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay