SWE Prep

Share this post

Single Number

sweprep.substack.com

Single Number

Sameer Khoja
Mar 31, 2021
Share this post

Single Number

sweprep.substack.com

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

Solution

Approach 1: Hash Table

We use hash table to avoid the O(n) time required for searching the elements.

  1. Iterate through all elements in nums and set up key/value pair.

  2. Return the element which appeared only once.

See Approach 1

Approach 2: Math

We can use the following equation to solve the problem:

2 ∗ ( a + b + c ) − ( a + a + b + b + c ) = c

See Approach 2

Share this post

Single Number

sweprep.substack.com
TopNew

No posts

Ready for more?

© 2023 Sameer Khoja
Privacy ∙ Terms ∙ Collection notice
Start WritingGet the app
Substack is the home for great writing