Intro
This is the second part of the kata adventures: Find the odd (first part), in this blog I would provide a simple implementation in javascript. (in the end I will provide you a mind blowing solution, no use of map!)
The problem
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.
(codewars.com problem, not mine)
Now the funny part, let's implement the solution!
Solution
In plain English the solution looked like the following:
1. initialise 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
What will need:
- A map
- iterate over an array
- check if the map contains a key
- retrieve value from a map based on a key
- set a value for a specific key
- iterate over a map
let's see how we can do it in javascript Engilsh -> js :)
Map initialisation:
let myMap = new Map()
, you could have used an object instead, here is a good comparison (Maps vs Objects)Map construct comes with the method
myMap.has(key)
, which in case that key is present returns true, otherwise falsemyMap.get(key)
, if the key is present returns the corresponding value, otherwiseundefined
myMap.set(key, value)
, set the a value for a specified key
let's put all together and form the solution:
The special solution!
Magic happened! XOR everything! I didn't thought of it, but it was really cool!