recursion/greatest_common_divisor.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem\n",
    "Given n numbers, find the greatest common denominator between them.\n",
    "\n",
    "For example, given the numbers [42, 56, 14], return 14\n",
    "\n",
    "## Solution\n",
    "Because the greatest common divisor is associative, gcd of multiple numbers: say `a, b, c` is equivalent to \n",
    "```\n",
    "gcd(gcd(ab),c)\n",
    "```\n",
    "By definition, if the divisor divides gcd(a, b) and c, it must divide a and b as well.\n",
    "\n",
    "The GCD of multiple numbers `a, b, ... n` can be obtained by **iteratively computing the GCD of `a and b`, and GCD of the result of that with `c` and so on.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gcd(numbers):\n",
    "    n = numbers[0]\n",
    "    for num in numbers[1:]:\n",
    "        n = _gcd(n, num)\n",
    "    return n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A naive implementation might try every integer from 1 to min(a, b) and see of it divides the larger:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def _gcd_naive(a, b):\n",
    "    # find smallest value, largest value of the two\n",
    "    smaller, larger = min(a, b), max(a,b)\n",
    "    # iteratively check every integer from the smallest value to 1.\n",
    "    for divisor in range(smaller, 0, -1):\n",
    "        if larger % divisor == 0:\n",
    "            return divisor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A more efficient method is the Euclidean algorithm which follows a recursive formula:\n",
    "\n",
    "```\n",
    "gcd(a, 0) = a\n",
    "gcd(a, b) = gcd(b, a % b)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def _gcd(a, b):\n",
    "    if b == 0:\n",
    "        return a\n",
    "    return _gcd(b, a % b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# time to test it out\n",
    "gcd([42, 56, 14, 7])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's a more memory-efficient method that works bottom up:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "64"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def _gcd(a, b):\n",
    "    while b:\n",
    "        a, b = b, a % b\n",
    "    return a\n",
    "\n",
    "# test it out\n",
    "gcd([0, 64, 256, 128])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For more details check out this video tutorial on how [Euclidean algorithm](https://www.youtube.com/watch?v=p5gn2hj51hs) works."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}