Single Number

#beginners #programming #interview #career

Here is a simple problem dealing with arrays.

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

Example 1:

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

Example 2:

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

There are a couple of ways on how to deal with this problem the easiest approach, in my opinion, is to use a dictionary.

Using a Dictionary:

Dictionaries allow you to store key-value pairs allowing us to store a number and the count of times you see the number. Now there are a couple of ways to implement a dictionary if you want to create your own but here I am going to use the built-in one. Using this method allows for an O(n) BigO notation but does use memory.

2 For Loop solution:

One way to do it without using much extra memory is to use a double for loop to go through the array. Going through the array once you find a duplicate you can change the digit to undefined. If you pass through the list without finding a duplicate you can return it. Note this will destroy the integrity of the list as you are changing values.

There are a couple of other ways to solve this problem so put your solution down below! Thanks for reading, like and follow for more! 🙃