{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "0cb5777e",
   "metadata": {},
   "source": [
    "# \"Problem 1: Multiples of 3 and 5\"\n",
    "> Utilitize the basic properties of multiples and sums.\n",
    "\n",
    "- permalink: p1\n",
    "- toc: true\n",
    "- badges: true\n",
    "- comments: true\n",
    "- categories: [solution]"
   ]
  },
  {
   "source": [
    "## 🔒 [Problem](https://projecteuler.net/problem=1)\n",
    "\n",
    "If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.\n",
    "\n",
    "Find the sum of all the multiples of 3 or 5 below 1000.\n",
    "\n",
    "### 🔐 Key Idea\n",
    "using mathematical concepts to reduce the iteration number"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "markdown",
   "id": "74b3c82b",
   "metadata": {},
   "source": [
    "## 🔑 Solution\n",
    "\n",
    "### 🧭 Initial idea\n",
    "\n",
    "$O(1)$ complexity.\n",
    "\n",
    "Using the mathematical concept of sum of multiples exists as a pair in a range. \n",
    "\n",
    "For example, for the sum of multiples of 2 not exceeding 8, there would be 5 pairs with equal sum: (2, 8), (4, 6). These pairs sum to 2 + 8, which is the minimum and the maximum multiple. Numbers with odd number of multiples, we can just add `(min + max) // 2` to the sum."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "9a37da86",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "233168\n"
     ]
    }
   ],
   "source": [
    "# Target number used to limit iteration\n",
    "k = 999\n",
    "\n",
    "f = [3, 5, 15]  # factors\n",
    "n = [k//3, k//5, k//15]  # number of multiples\n",
    "max = [k - k%3, k - k%5, k - k%15]  # biggest multiples for each factor \n",
    "sum = []  # sum of each factors\n",
    "\n",
    "for i in range(3):\n",
    "    minmax = f[i] + max[i]\n",
    "    s = (n[i] // 2) * minmax\n",
    "\n",
    "    if n[i] % 2 is 1:\n",
    "        s += minmax // 2\n",
    "\n",
    "    sum.append(s)\n",
    "\n",
    "print(str(sum[0] + sum[1] - sum[2]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f496ecd3",
   "metadata": {},
   "source": [
    "> WARNING: Since it's defined in the problem as *'below 1000'*, it shouldn't contain 1000.\n",
    "\n",
    "<br/>\n",
    "\n",
    "> TIP: Consider the range with operands such as `<`, `>`, etc.\n",
    "\n",
    "<br/>\n",
    "\n",
    "> NOTE: Clarify the *range* of the problem before diving into it."
   ]
  },
  {
   "source": [
    "### 🔨 Bruteforce method\n",
    "\n",
    "$O(n)$ complexity."
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "233168\n"
     ]
    }
   ],
   "source": [
    "s = 0\n",
    "for i in range(1000):\n",
    "    if i % 3 is 0 or i % 5 is 0:\n",
    "        s += i\n",
    "\n",
    "print(s)"
   ]
  },
  {
   "source": [
    "### 🔁 Function method (from overview)\n",
    "\n",
    "$O(1)$ complexity.\n",
    "\n",
    "> TIP: Use functons or external blocks for complicated for loops or loops with small iteration count."
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "233168\n"
     ]
    }
   ],
   "source": [
    "k = 999\n",
    "\n",
    "def get_multiple_sum(f):\n",
    "    n = k // f\n",
    "    max = k - k % f\n",
    "    sum = (f + max) * (n // 2)\n",
    "\n",
    "    if n % 2 is 1:\n",
    "        sum += (f + max) // 2\n",
    "\n",
    "    return sum\n",
    "\n",
    "print(str(get_multiple_sum(3) + get_multiple_sum(5) - get_multiple_sum(15)))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "python374jvsc74a57bd0b39ab04170b6c60b52a31d4a7ab4d204539d261a537423dd50ae2a4297d5cc93",
   "display_name": "Python 3.7.4 32-bit"
  },
  "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": 5
}