Recursion_BigO_List_Array.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Recursion_BigO_List_Array.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyNlK2FzfAR2uyytZjUzzpFx",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/Machine-Learning-Moron/DataStructures-Python/blob/faang/Recursion_BigO_List_Array.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "R97FNVV_P0mo"
      },
      "source": [
        "RECURSION"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "k1VaHFJnP4To",
        "outputId": "6eecaeb2-f1ee-4061-efea-12944389dba7"
      },
      "source": [
        "# Question 1\n",
        "def sumofDigits(n):\n",
        "    assert n>=0 and int(n) == n , 'The number has to be a postive integer only!'\n",
        "    if n == 0:\n",
        "        return 0\n",
        "    else:\n",
        "        return int(n%10) + sumofDigits(int(n/10))\n",
        "\n",
        "print(sumofDigits(11111))"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "5\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "qjvv9dGeQEIm",
        "outputId": "c0dbb0ba-ae4d-419f-a636-03ed3aa0e3dd"
      },
      "source": [
        "#Question 2\n",
        "\n",
        "def power(base,exp):\n",
        "    if exp == 0:\n",
        "        return 1\n",
        "    if(exp==1):\n",
        "        return(base)\n",
        "    if(exp!=1):\n",
        "        return (base*power(base,exp-1))\n",
        "\n",
        "print(power(4,2))"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "16\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "I8bTSLbDQNyI",
        "outputId": "89e70952-6c23-46fe-e918-d6b6a69c459c"
      },
      "source": [
        "# Question 3\n",
        "\n",
        "\n",
        "def gcd(a, b):\n",
        "    assert int(a) == a and int(b) == b, 'The numbers must be integer only!'\n",
        "    if a < 0:\n",
        "        a = -1 * a\n",
        "    if b < 0:\n",
        "        b = -1 * b\n",
        "    if b == 0:\n",
        "        return a\n",
        "    else:\n",
        "        return gcd(b, a%b)\n",
        "\n",
        "print(gcd(12,5))"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "sSmLCVsGQThh",
        "outputId": "b41f1d44-c5da-4f40-81de-62982edcc394"
      },
      "source": [
        "# Question 4\n",
        "def binaryToDemical(n):\n",
        "    if n == 0:\n",
        "        return 1\n",
        "    else:\n",
        "        return n%2 + 10*binaryToDemical(int(n/2))\n",
        "\n",
        "\n",
        "print(binaryToDemical(1))"
      ],
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "11\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XBjXUU-7Ql5J"
      },
      "source": [
        "### Big O"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 51
        },
        "id": "ZrTZ-G_MQdt-",
        "outputId": "9fe184b6-9a48-4eee-a456-e99e458c27b4"
      },
      "source": [
        "#Question1\n",
        "def foo(array):\n",
        "    sum = 0 \n",
        "    product = 1 \n",
        "    for i in array:\n",
        "        sum += i\n",
        "    for i in array:\n",
        "        product *= i\n",
        "    print(\"Sum = \"+str(sum)+\", Product = \"+str(product))\n",
        "\n",
        "ar1 = [1,2,3,4]\n",
        "foo(ar1)\n",
        "\n",
        "'''\n",
        "TIME COMPLEXITY = O(N)\n",
        "'''"
      ],
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Sum = 10, Product = 24\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            },
            "text/plain": [
              "'\\nTIME COMPLEXITY = O(N)\\n'"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 11
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "id": "nW5cUG24RB2C",
        "outputId": "b0c80f7b-3f80-4a84-ce54-52bbf5d186d6"
      },
      "source": [
        "def printPairs(array):\n",
        "    for i in array:\n",
        "        for j in array:\n",
        "            print(str(i)+\",\"+str(j))\n",
        "\n",
        "'''\n",
        "TIME COMPLEXITY = O(N^2)\n",
        "'''"
      ],
      "execution_count": 10,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            },
            "text/plain": [
              "'\\nTIME COMPLEXITY = O(N^2)\\n'"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 10
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "id": "pM6sWDA-f8vE",
        "outputId": "334791f5-2d58-4050-d9c7-c8a485e9ecdf"
      },
      "source": [
        "def printUnorderedPairs(array):\n",
        "    for i in range(0,len(array)):\n",
        "        for j in range(i+1,len(array)):\n",
        "            print(array[i] + \",\" + array[j])\n",
        "\n",
        "\n",
        "'''\n",
        "TIME COMPLEXITY = O(N^2)\n",
        "'''"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            },
            "text/plain": [
              "'\\nTIME COMPLEXITY = O(N^2)\\n'"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 9
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "id": "5NqlyGHEgfZX",
        "outputId": "7a7d8531-44b2-4e45-9f1f-8fcf8fd37cf1"
      },
      "source": [
        "def printUnorderedPairs(arrayA, arrayB):\n",
        "    for i in range(len(arrayA)):\n",
        "        for j in range(len(arrayB)):\n",
        "            if arrayA[i] < arrayB[j]:\n",
        "                print(str(arrayA[i]) + \",\" + str(arrayB[j]))\n",
        "\n",
        "arrayA = [1,2,3,4,5]\n",
        "arrayB = [2,6,7,8]\n",
        "\n",
        "'''\n",
        "TIME COMPLEXITY = O(AB)\n",
        "'''"
      ],
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            },
            "text/plain": [
              "'\\nTIME COMPLEXITY = O(AB)\\n'"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 12
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 34
        },
        "id": "Fac7PonBgz9d",
        "outputId": "85f90132-1b8c-4225-ee03-217d2600aa3c"
      },
      "source": [
        "#Question5\n",
        "def printUnorderedPairs(arrayA, arrayB):\n",
        "    for i in range(len(arrayA)):\n",
        "        for j in range(len(arrayB)):\n",
        "            for k in range(0,100000):\n",
        "                print(str(arrayA[i]) + \",\" + str(arrayB[j]))\n",
        "\n",
        "'''\n",
        "TIME COMPLEXITY = O(AB)\n",
        "'''"
      ],
      "execution_count": 13,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            },
            "text/plain": [
              "'\\nTIME COMPLEXITY = O(AB)\\n'"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 13
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 51
        },
        "id": "wnjYztzIhFrL",
        "outputId": "f731aefa-e5b7-4702-8bc6-a644d36b6667"
      },
      "source": [
        "#Question6\n",
        "def reverse(array):\n",
        "    for i in range(0,int(len(array)/2)):\n",
        "        other = len(array)-i-1\n",
        "        temp = array[i]\n",
        "        array[i] = array[other]\n",
        "        array[other] = temp\n",
        "    print(array)\n",
        "\n",
        "reverse(arrayA)\n",
        "\n",
        "'''\n",
        "TIME COMPLEXITY = O(N)\n",
        "'''"
      ],
      "execution_count": 15,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[1, 2, 3, 4, 5]\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            },
            "text/plain": [
              "'\\nTIME COMPLEXITY = O(N)\\n'"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 15
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 51
        },
        "id": "v0mcFNV4hKZC",
        "outputId": "8d8445a2-018e-428b-a6c6-e04a1576fd07"
      },
      "source": [
        "#Question7\n",
        "\n",
        "def factorial(n):\n",
        "    if n < 0:\n",
        "        return -1\n",
        "    elif n == 0:\n",
        "        return 1\n",
        "    else:\n",
        "        return n * factorial(n-1)\n",
        "\n",
        "print(factorial(3))\n",
        "\n",
        "\n",
        "'''\n",
        "TIME COMPLEXITY = O(N)\n",
        "'''"
      ],
      "execution_count": 16,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "6\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            },
            "text/plain": [
              "'\\nTIME COMPLEXITY = O(N)\\n'"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 16
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 101
        },
        "id": "DUFQB2h9hrwb",
        "outputId": "b1d5727d-265c-43fb-89fd-df2ab6d17adf"
      },
      "source": [
        "#Question8\n",
        "def allFib(n):\n",
        "    for i in range(n):\n",
        "        print(str(i)+\":, \" + str(fib(i)))\n",
        "\n",
        "def fib(n):\n",
        "    if n <= 0:\n",
        "        return 0\n",
        "    elif n == 1:\n",
        "        return 1\n",
        "    return fib(n-1) + fib(n-2)\n",
        "allFib(4)\n",
        "\n",
        "\n",
        "'''\n",
        "TIME COMPLEXITY = O(2^N)\n",
        "'''"
      ],
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "0:, 0\n",
            "1:, 1\n",
            "2:, 1\n",
            "3:, 2\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            },
            "text/plain": [
              "'\\nTIME COMPLEXITY = O(2^N)\\n'"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 17
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 217
        },
        "id": "hH4DKeBPiJMJ",
        "outputId": "c82dd66c-7ede-485f-9073-0a8854f051eb"
      },
      "source": [
        "#Question9\n",
        "def powersOf2(n):\n",
        "    # print(\"n:\"+str(n))\n",
        "    if n < 1:\n",
        "        return 0\n",
        "    elif n == 1:\n",
        "        print(1)\n",
        "        return 1\n",
        "    else:\n",
        "        prev = powersOf2(int(n/2))\n",
        "        # print(\"prev:\"+str(prev))\n",
        "        print(prev)\n",
        "        curr = prev*2\n",
        "        print(curr)\n",
        "        return curr\n",
        "\n",
        "powersOf2(50)\n",
        "\n",
        "'''\n",
        "TIME COMPLEXITY = O(logN)\n",
        "'''"
      ],
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1\n",
            "1\n",
            "2\n",
            "2\n",
            "4\n",
            "4\n",
            "8\n",
            "8\n",
            "16\n",
            "16\n",
            "32\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "application/vnd.google.colaboratory.intrinsic+json": {
              "type": "string"
            },
            "text/plain": [
              "'\\nTIME COMPLEXITY = O(logN)\\n'"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 18
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "6-BvgQeIimzp"
      },
      "source": [
        "### LIST AND ARRAY"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "36vEr80LiYCN",
        "outputId": "ab35e57c-402e-4822-9568-528545c9c14f"
      },
      "source": [
        "#  Question 1\n",
        "\n",
        "mylist = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]\n",
        "\n",
        "\n",
        "def findMissing(list, n):\n",
        "    sum1 = sum(list)\n",
        "    sum2 = 100*101/2\n",
        "    print(sum2-sum1)\n",
        "\n",
        "\n",
        "findMissing(mylist, 100)"
      ],
      "execution_count": 19,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "73.0\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "fwh1AaiZiuKh",
        "outputId": "54e8b7d0-f200-45cb-b231-efed355b0590"
      },
      "source": [
        "# Question 2\n",
        "def findPairs(list, sum):\n",
        "    for i in range(len(list)):\n",
        "        for j in range(i+1,len(list)):\n",
        "            if (list[i]+list[j]) == sum:\n",
        "                print(list[i],list[j])\n",
        "findPairs(mylist, 100)"
      ],
      "execution_count": 21,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1 99\n",
            "2 98\n",
            "3 97\n",
            "4 96\n",
            "5 95\n",
            "6 94\n",
            "7 93\n",
            "8 92\n",
            "9 91\n",
            "10 90\n",
            "11 89\n",
            "12 88\n",
            "13 87\n",
            "14 86\n",
            "15 85\n",
            "16 84\n",
            "17 83\n",
            "18 82\n",
            "19 81\n",
            "20 80\n",
            "21 79\n",
            "22 78\n",
            "23 77\n",
            "24 76\n",
            "25 75\n",
            "26 74\n",
            "28 72\n",
            "29 71\n",
            "30 70\n",
            "31 69\n",
            "32 68\n",
            "33 67\n",
            "34 66\n",
            "35 65\n",
            "36 64\n",
            "37 63\n",
            "38 62\n",
            "39 61\n",
            "40 60\n",
            "41 59\n",
            "42 58\n",
            "43 57\n",
            "44 56\n",
            "45 55\n",
            "46 54\n",
            "47 53\n",
            "48 52\n",
            "49 51\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "pMOxh5zYi1e-",
        "outputId": "1c5cabd0-f1ff-4132-fa58-71f80308955a"
      },
      "source": [
        "# Question 3\n",
        "import numpy as np \n",
        "myArray = np.array([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20])\n",
        "\n",
        "def findNumber(array, number):\n",
        "    for i in range(len(array)):\n",
        "        if array[i] == number:\n",
        "            print(i)\n",
        "\n",
        "findNumber(myArray, 12)"
      ],
      "execution_count": 22,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "11\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "0iLfFlnSi8EN",
        "outputId": "c4926e58-7ba3-4c17-ffc1-a48318ce9757"
      },
      "source": [
        "# Question 4\n",
        "\n",
        "def findMaxProduct(array):\n",
        "    maxProduct = 0\n",
        "    for i in range(len(array)):\n",
        "        for j in range(i+1,len(array)):\n",
        "            if array[i]*array[j] > maxProduct:\n",
        "                maxProduct = array[i]*array[j]\n",
        "                pairs = str(array[i])+ \",\" + str(array[j])\n",
        "    print(pairs)\n",
        "    print(maxProduct)\n",
        "\n",
        "findMaxProduct(myArray)\n"
      ],
      "execution_count": 23,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "19,20\n",
            "380\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "FGRao9vRjBXB",
        "outputId": "6dea7eb0-74cf-438a-ff9e-ed0f3aed2e73"
      },
      "source": [
        "#Question 5\n",
        "mylist = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100]\n",
        "def isUnique(list):\n",
        "  a=[]\n",
        "  for i in list:\n",
        "    if i in a:\n",
        "        print(i)\n",
        "        return False\n",
        "    else:\n",
        "        a.append(i)\n",
        "  return True\n",
        "\n",
        "print(isUnique(mylist))\n"
      ],
      "execution_count": 28,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "True\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}