{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "Given a positive integer `n`, you can apply one of the following operations:\n",
    "\n",
    "  1. If `n` is even, replace `n` with `n / 2`.\n",
    "  2. If `n` is odd, replace `n` with either `n + 1` or `n - 1`.\n",
    "\n",
    "Return _the minimum number of operations needed for`n` to become `1`_.\n",
    "\n",
    "\n",
    "\n",
    "**Example 1:**\n",
    "\n",
    "\n",
    "\n",
    "    Input: n = 8\n",
    "    Output: 3\n",
    "    Explanation: 8 -> 4 -> 2 -> 1\n",
    "\n",
    "\n",
    "**Example 2:**\n",
    "\n",
    "\n",
    "\n",
    "    Input: n = 7\n",
    "    Output: 4\n",
    "    Explanation: 7 -> 8 -> 4 -> 2 -> 1\n",
    "    or 7 -> 6 -> 3 -> 2 -> 1\n",
    "\n",
    "\n",
    "**Example 3:**\n",
    "\n",
    "\n",
    "\n",
    "    Input: n = 4\n",
    "    Output: 2\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "**Constraints:**\n",
    "\n",
    "  * `1 <= n <= 231 - 1`"
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "integer_replacement (generic function with 1 method)"
     },
     "metadata": {},
     "execution_count": 1
    }
   ],
   "cell_type": "code",
   "source": [
    "# @lc code=start\n",
    "using LeetCode\n",
    "\n",
    "function integer_replacement(n::Int)\n",
    "    res = 0\n",
    "    while n != 1\n",
    "        if iseven(n)\n",
    "            n >>= 1\n",
    "        else\n",
    "            n += (n & 2 == 0 || n == 3) ? -1 : 1\n",
    "        end\n",
    "        res += 1\n",
    "    end\n",
    "    return res\n",
    "end\n",
    "# @lc code=end"
   ],
   "metadata": {},
   "execution_count": 1
  },
  {
   "cell_type": "markdown",
   "source": [
    "---\n",
    "\n",
    "*This notebook was generated using [Literate.jl](https://github.com/fredrikekre/Literate.jl).*"
   ],
   "metadata": {}
  }
 ],
 "nbformat_minor": 3,
 "metadata": {
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.10.1"
  },
  "kernelspec": {
   "name": "julia-1.10",
   "display_name": "Julia 1.10.1",
   "language": "julia"
  }
 },
 "nbformat": 4
}