algorithm: to a simple rhythm

Han
Han
Nov 11, 2020 · 8 min read

in the grand scheme of things, i am infantile;

but even children learn and understand important math related concepts.

algorithms are step-by-step instructions on how to solve a problem, they can vary based on efficiency. efficiency in this context means accuracy, speed, and processing power needed.

in the software engineering system, there are many different way to solve a problem. on this medium page, the dedicated developer who keeps learning about these vicious algorithms is a member of an elite squad. this is her attempt at solving these problems…

note: the proceeding code snippets are all in Python. i’ve always had a thing for reptiles. i’ll be referring to arrays as ‘lists’ because that is the correct term in Python.

greatest common divisor & least common multiple

euclid’s algorithm

greatest common divisor (gcd): the largest possible integer that can divide two provided integers
least common multiple (lcm): the smallest possible number that is a multiple of two or more integers

def gcd(a, b):
if a % b == 0:
return b
else:
c = a % b
return gcd(b, c)
def lcm(a, b):
return (a * b) // gcd(a, b)
  1. define the function gcd, which takes two parameters, a & b
  2. define a conditional statement checking to see if a is equally divisible by b. a mod of 0 means there was nothing left over from the division
  3. if a was evenly divided by b, then return b as your greatest common divisor
  4. if the statement on line 2 doesn’t evaluate true, this will execute instead
  5. store the modulus value of a divided by b in a new variable, c
  6. while still inside the gcd function, invoke the gcd function with the new values of b and c, this will trigger the function to perform all the same calculations until line 2 is met
  7. define a new function, lcm, with two parameters, a & b
  8. return the formula for calculating the least common multiple, which is (a*b)/gcd(a,b)

fibonacci

the fibonacci sequence to f(20)

the fibonacci numbers follow a simple pattern and start with 0 and 1. 0 + 1 = 1, which makes the second number in the sequence also 1. now you add 1 + 1 = 2, so 2 is the third number in the sequence. 1 + 2 = 3, making 3 the fourth number. 2 + 3 = 5, meaning 5 is the fifth number in the sequence. so on and so forth. this sequence was actually noticed by the western world when a mathematician, Fibonacci, used it in a book to calculate the growth of a rabbit population.

there is a very simple formula to calculate a fibonacci number!
f(n-1)+f(n-2): where f(n) directly refers to the sequence in the chart above. this formula can be implemented in a program using a recursive function. a recursive function keeps a call to itself in its own code body, and repeats the overall function until a specific condition, or base case, it met.

this looks sleek and easy. but recursive functions could take a lot of time if you are looking for a bigger number. the calculation will have to be done so many times over, which gives us O(N) for space complexity because we have to cycle through as many times as N, our parameter. and O(2^n) for time complexity which is pretty horrible.

if we adjusted our logic and took the linear approach instead, we could reduce our space complexity to O(1) and out time complexity to just O(N) because you’re just looping through as many integers as N once.

def fib(n):
a, b = 0, 1
for i in range(0, n):
temp = a
a = b
b = temp + b
return a
  1. define the functions’ name, fib, and what parameter it will have, n
  2. set the first variable, a, to be 0 and the second variable, b, to 1; mimicking the order of the fibonacci sequence
  3. create a for loop, starting at 0 and ending at the value of the parameter, n
  4. create a temporary variable with the value of a. (temp = 0)
  5. give a the value of b, which essentially starts moving focus to the right in the sequence (now a = 1)
  6. give b a new value of the temporary value + b’s current value (now b = 0 + 1 = 1)
  7. outside of the loop, return the value of a as the fibonacci number that corresponds with the given argument of n

get last digit of a fibonacci number

i can’t tell you exactly why you would use this, but who am i to deprive you from knowledge.

def fib_last_digit(n):
if n < 2:
return n
else:
a, b = 0, 1
for i in range(1, n):
a, b = b, (a + b) % 10
return b
  1. define a function that takes one parameter, n
  2. set up conditional logic to check if n is less than 2
  3. if that is true, return the number n because there are no further calculations to be done
  4. if that condition was not met then…
  5. create and initialize two new variables, a & b, and set them to 0 & 1 respectively
  6. outside of the conditional block, create a for loop using the range of 1 to n
  7. mimicking the logic in our fib function from above, we update the values of a and b to be b and (a+b) % 10 respectively. the last line of code will produce the last digit of the number
  8. return b outside of the for loop

calculate change back

this is based on simple calculation cashiers do in their head everyday. if you can only give someone change back in dimes, nickels, and pennies, how do you handle each situation?

def get_change(m):
count = 0
if m % 10 == 0:
count = m // 10
return count
while m > 10:
m -= 10
count += 1
while m >= 5:
m -= 5
count += 1
while m > 0:
m -= 1
count += 1
if m == 0:
count += 0
return count
  1. define a function that takes a value of change to give back, m
  2. create a variable count that starts at 0
  3. conditional logic to see if m is evenly divisible by 10
  4. if so, the count is equal to m/10 number of dimes
  5. return the new value for count and end the function
  6. outside of the if statement, create a while loop that works as long as m is greater than 10
  7. remove 10 from m and update m each loop
  8. increment count by 1
  9. outside of the last while statement, write a new one form > 5
  10. remove 5 from m and update m with each loop
  11. increment count by 1
  12. outside the last while statement, write a new one for m > 0
  13. remove 1 from m and update m
  14. increment count by 1
  15. for finishing touches, you can check if m equals 0
  16. nothing to update on the count
  17. outside and after all those conditionals and loops, return count

car fueling

a visual rep of the this greedy algorithm

the prompt for this function is simple, you need to figure out how many refills your car needs on a road trip. you need to know the overall distance, the miles per tank for the car, and a list of the mile markers for the potential gas station stops.

def min_refills(distance, miles, stops):
n = len(stops)
num_refill, curr_refill, limit = 0, 0, miles
while limit < distance:
if curr_refill >= n or stops[curr_refill] > limit:
return -1
while curr_refill < n - 1 and stops[curr_refill + 1] <= limit:
curr_refill += 1
num_refill += 1
limit = stops[curr_refill] + miles
curr_refill += 1
return num_refill
  1. define a function that takes your total traveling distance, the miles you can travel on one tank of gas, and a list of stops sorted by the distance from your starting point.
  2. create a variable n that is equal to the number of available stops
  3. create variables to track the times you have refilled, your current refill status, and what your current limit is.
  4. as long as your distance is greater than your limit
  5. if your current refill variable is greater than or equal to n (# of stops) OR if the next stop is greater than the current limit then…
  6. return -1 because you cannot make it with the given parameters
  7. outside of the if statement, but still inside the first while loop, create a second while loop that checks if the current refill is less than n — 1 AND the next stop is less than or equal to the current limit
  8. the while loop should return a new current refill count, incrementing and updating by 1
  9. outside of the second while, but still inside the first, increment and update the number of refills by 1
  10. update the current limit to reflect the current stop + the miles per tank
  11. increment and update current refill by 1
  12. outside of the while loop, return the total number of refills

largest number

how to return the largest number by combining strings of numbers. a simple and popular scenario for this algorithms use is negotiating salary. imagine your boss wrote down a random series of numbers and then tasked you to reorder them however you like, as that would be your new salary. you obviously want to make the biggest number possible, and here’s how.

def largest_number(digits):
res = ''
empty_list = []
l = len(str(max(digits))) + 1
for i in digits:
temp = str(i) * l
empty_list.append((temp[:l:], i))
empty_list.sort(reverse=True)
for i in empty_arr:
res += str(i[1])
if int(res) == 0:
return "0"
return res
  1. define a function that takes in a list of digits
  2. create a variable for your result, it can be an empty string to start
  3. create an empty list to store the values in
  4. find the max digit from the digits list, convert that digit to a string data type, find the length of that string and add 1. store that code in a variable. this number will come in handy as something we can use to evaluate all integers in an even way
  5. create a for loop to iterate through digits
  6. inside the for loop, create a temporary variable to store the each version of i * l, which create a repetition of the digits. this is the secret to accurately comparing numbers for this specific outcome. when all the numbers are the same length, it can be sorted
  7. add the whole temp variable and the original digit to the empty list
  8. outside of the for loop, sort the now-not-so-empty list in reverse order
  9. create a new for loop to iterate through the now-not-so-empty list
  10. update the empty result string with values from the now-not-so-empty list. the number 1 in brackets refers to the first index of each element in the now-not-so-empty list. the first index is actually the the original number from the digits list, not the repeated number, which is just used to sort the list.
  11. outside of the for loop, create logic to check if the result string has a value of zero
  12. if it does, return 0 in a string
  13. outside of that conditional and at the end of the function, return the completed result string

if you made it this far, thank you :) that was a lot of information but those are definitely some useful calculations to have at the ready. i’m still in the beginning of my journey but learning about algorithms has been really rewarding (and challenging, but that has a more to do with meeting testing standards). i’m feeling more confident everyday and seeing more and more connections. i hope these articles help you as much as they help me.

Nerd For Tech

Technical Media House

Han

Written by

Han

somewhere between lisa simpson and lana del rey

Nerd For Tech

We are tech nerds because we believe in reinventing the world with the power of Technology. Our articles talk about some of the most disruptive ideas, technology, and innovation.

Han

Written by

Han

somewhere between lisa simpson and lana del rey

Nerd For Tech

We are tech nerds because we believe in reinventing the world with the power of Technology. Our articles talk about some of the most disruptive ideas, technology, and innovation.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store