Kata adventures: Find the odd, first part (Map data structure)
Tags: fundamentals, map
Published: 2020-05-10 13:45:46

## 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]] (the input)

(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.