Kata adventures: Find the odd, first part (Map data structure)

Intro

Hello dev.to world!! I would like to say just a few words about my
motivation of doing this series and for what is it about.

My name is Konstantinos and I am a professional developer for
almost 5 years, what brought me in this field is the excitement of
solving problems by writting code (good or bad).

What I wanted to do with this blog is to share the way I am thinking
about a problem, the different aproaches that you can take to tackle
it and all this thinking process that we experience till the solution
(the one that you think that is the best or right one).

The problem: find the odd (Map power)

Most of the problems are not mine, this problem was taken from codewars.com.

Let's dive into the first problem!

problem description:

Given an array of integers, find the integer that appears an odd number of times.

There will always be only one integer that appears an odd number of times.

Step 1

read the problem really carefully and then to extract
the input and the output of the problem.

• input: an array of integers
• ouput: an integer

Step 2

Next spot keywords that will make you to choose the right tools

• there is the keyword find, so you will need some search mechanism
• then follows: appears an odd number of times, this indicates a need to keep track how many times some integer appears

Step 3

find a data structure that might be suitable for the problem.
One data structure that might be usefull in this problem is a map.

A Map is a data structure that can holds key value pairs, with the following properties:

• Each key is unique
• Fast value retrieval by using a key (fast read)
• Fast value write by using a key (fast write)
• You cannot have duplicate keys

We could use this data structure by storing the input array values as map keys and as values how often they appear in the array, then we can iterate over the map to get the number which is repeated odd times, let's write down the logic in pseudo code:

1. initialize a map (an empty key, value storage)
2. iterate over the array
   1. if the map does not contain the array value as key
      1. put the value as key and the value of it set it to 0
   2. else
      1. get the previous value using the array value (__Fast value retrieval__)
      2. add one to the previous value
3. iterate over the map
   1. if you find a integer that is repeated odd times finish and return it

let's demonstrate it with a concrete example with the above logic:

Given an integer array [1, 2, 1]

(demonstration of step 2, assume that we have initialize an empty map)

first iteration:

we are facing the number 1, the map is empty so in the map will have the the key pair (1, 1) (value 1 and number of occurances 1)

second iteration:

number 2 is next, the map contains only the previous pair, number 2 is not present, so a pair of (2, 1) is added now the map contains the pairs: (1, 1), (2, 1)

third iteration:

the final number is the 1, 1 is already a key in the map, so we increase the previous value by on, the updated pair will be (1, 2)

In the end we will end up with a map like this: (1, 2), (2, 1)

(demonstration of step 3, iterating over a map)

first iteration:

we have the key 1 and value of 2, which is not an odd so we have to continue to the next pair

second iteration:

we have the key 2 and value of 1, which is an odd so the program returns the key as a result!! Great success!!

Summary:

In this blog post we examined a power data structure called map!
Which has some amazing powers:

• fast read based on key
• fast write based on key
• each key is unique
• you cannot have duplicates

In the next blog spot I will implement this problem with python and javascript.