# algorithm: to a simple rhythm

# 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

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)

- define the function
*gcd*, which takes two parameters,*a*&*b* - 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 - if
*a*was evenly divided by*b*, then return*b*as your greatest common divisor - if the statement on line 2 doesn’t evaluate true, this will execute instead
- store the modulus value of
*a*divided by*b*in a new variable,*c* - 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 - define a new function,
*lcm*, with two parameters,*a*&*b* - return the formula for calculating the least common multiple, which is
`(a*b)/gcd(a,b)`

## fibonacci

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

- define the functions’ name,
*fib*, and what parameter it will have,*n* - set the first variable,
*a*, to be 0 and the second variable,*b*, to 1; mimicking the order of the fibonacci sequence - create a for loop, starting at 0 and ending at the value of the parameter,
*n* - create a
*temp*orary variable with the value of*a*. (*temp*= 0) - give
*a*the value of*b*, which essentially starts moving focus to the right in the sequence (now*a*= 1) - give b a new value of the
*temp*orary value +*b*’s current value (now*b*= 0 + 1 = 1) - 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

- define a function that takes one parameter,
*n* - set up conditional logic to check if
*n*is less than 2 - if that is true, return the number
*n*because there are no further calculations to be done - if that condition was not met then…
- create and initialize two new variables,
*a*&*b*, and set them to 0 & 1 respectively - outside of the conditional block, create a for loop using the range of 1 to
*n* - 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 - 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

- define a function that takes a value of change to give back,
*m* - create a variable
*count*that starts at 0 - conditional logic to see if
*m*is evenly divisible by 10 - if so, the
*count*is equal to*m/10*number of dimes - return the new value for
*count*and end the function - outside of the if statement, create a while loop that works as long as
*m*is greater than 10 - remove 10 from
*m*and update*m*each loop - increment
*count*by 1 - outside of the last while statement, write a new one for
`m > 5`

- remove 5 from
*m*and update*m*with each loop - increment
*count*by 1 - outside the last while statement, write a new one for
`m > 0`

- remove 1 from
*m*and update*m* - increment
*count*by 1 - for finishing touches, you can check if
*m*equals 0 - nothing to update on the
*count* - outside and after all those conditionals and loops, return
*count*

## car fueling

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

- 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. - create a variable
*n*that is equal to the number of available*stops* - create variables to track the times you have
*refilled*, your*current refill*status, and what your current*limit*is. - as long as your
*distance*is greater than your*limit*… - 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… - return -1 because you cannot make it with the given parameters
- 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* - the while loop should return a new
*current refill*count, incrementing and updating by 1 - outside of the second while, but still inside the first, increment and update the number of
*refills*by 1 - update the current
*limit*to reflect the current*stop*+ the*miles*per tank - increment and update
*current refill*by 1 - 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

- define a function that takes in a list of digits
- create a variable for your
*result*, it can be an empty string to start - create an
*empty**list*to store the values in - 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 - create a for loop to iterate through
*digits* - 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 - add the whole
*temp*variable and the original digit to the*empty list* - outside of the for loop, sort the now-not-so-
*empty list*in reverse order - create a new for loop to iterate through the now-not-so-
*empty list* - 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. - outside of the for loop, create logic to check if the
*result*string has a value of zero - if it does, return 0 in a string
- 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.