In: Computer Science
PYTHON: Develop an algorithm for finding the most frequently occurring value in a list of numbers. Use a sequence of coins. Place paper clips below each coin that count how many other coins of the same value are in the sequence. Give the pseudocode for an algorithm that yields the correct answer, and describe how using the coins and paper clips helped you find the algorithm.
Please solve in python!
Lets consider we have 4 coins
first coin : value = 1
second coin : value = 2
third coin : value = 5
fourth coin : value = 10
Creating a random sequence of coins :
1 1 2 1 10 2 5 10 10 5 2 1 1
To decide how many paper clips to be put below coins of value 1,
we need to count total number of coins with value as 1
so , count(coin of value 1) => 5
similarly ,repeat same thing for remaining coins,
count(coin of value 2) => 3
count(coin of value 5) => 2
count(coin of value 10) => 3
to find the coin with maximum occurance , we need to find the max of counts that we have found for each of the coins.
Find the code below explanation of each step given in comments :
python version used : 3.7.0
-----------------------------------------------------------------------------------------------------------------------------------
coins=[1,1,2,1,10,2,5,10,10,5,2,1,1] #input given to us is the sequence of coins
#step1
#counting number of similar coins by iterating over the list
#for storing the coin value and its occurance we will use a data
structure called dictionary (map in other languages)
occurance_map = {} #initializing an empty map , this map will have coin value as key and number of occurances as value
for i in range(0,len(coins)): #iterating over all the coins
if(coins[i] not in occurance_map.keys()): #if there is no entry of
that coin in occurance_map then make one and set the value to
1
occurance_map[coins[i]] = 1
else : #if there is already an entry of that coin then just
increase the value by 1
occurance_map[coins[i]] = occurance_map[coins[i]] + 1
#step 2
#once the occurance map is ready , the only thing remaining is
finding the key value pair where value is the highest
#we will do this by iterating over the disctionary
max_occurance = 0 #this variable keeps track of max occurance
coin_with_max_occurance = 0
for key in occurance_map:
if(occurance_map[key] > max_occurance): #if occurance of a coin
is greater than max_occurance then update the value of
max_occurance and coint_with_ma_occurance
coin_with_max_occurance = key
max_occurance = occurance_map[key]
print ("The coin which occured most number of times is :
"+str(coin_with_max_occurance))
print ("The total number of occurances is
:"+str(max_occurance))