Problems/1_Add_Two_Numbers.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 1. Add two numbers\n",
    "#-------------------------------------------------------------------\n",
    "#Given an array of integers nums and an integer target, \n",
    "#return indices of the two numbers such that they add up to target.\n",
    "\n",
    "#You may assume that each input would have exactly one solution, \n",
    "#and you may not use the same element twice.\n",
    "\n",
    "#You can return the answer in any order.\n",
    "#-------------------------------------------------------------------\n",
    "\n",
    "# example 1\n",
    "#----------\n",
    "# Input: nums = [1,3,5,2,7,11,15], target = 10\n",
    "# Output: [1,4]\n",
    "# Output: Because nums[1] + nums[4] == 10, we return [1, 4].\n",
    "#example 2\n",
    "#---------\n",
    "# Input: nums = [3,2,4,1], target = 7\n",
    "# Output: [0,2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " index i=0,j=1 target = 10 = 1 + 3\n",
      " index i=0,j=2 target = 10 = 1 + 5\n",
      " index i=0,j=3 target = 10 = 1 + 2\n",
      " index i=0,j=4 target = 10 = 1 + 7\n",
      " index i=0,j=5 target = 10 = 1 + 11\n",
      " index i=0,j=6 target = 10 = 1 + 15\n",
      " index i=1,j=2 target = 10 = 3 + 5\n",
      " index i=1,j=3 target = 10 = 3 + 2\n",
      " index i=1,j=4 target = 10 = 3 + 7\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(1, 4)"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Solving with FOR loops\n",
    "# Time  : O(n^2)\n",
    "# Space : O(1)\n",
    "\n",
    "nums = [1,3,5,2,7,11,15]\n",
    "target = 10\n",
    "\n",
    "def add_two_numbers(nums,target):\n",
    "    for i in range(len(nums)-1):\n",
    "        for j in range(i+1,len(nums)): # create all the combination\n",
    "            print(f\" index i={i},j={j} target = {target} = {nums[i]} + {nums[j]}\")\n",
    "            if target == nums[i] + nums[j]:\n",
    "                return i,j\n",
    "    return 0\n",
    "\n",
    "add_two_numbers(nums,target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 + 1 = 10\n",
      "5 + 7 = 10\n",
      "11 + 5 = 10\n",
      "3 + 7 = 10\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(1, 4)"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Solving random\n",
    "# Time  : O(1) - infinity\n",
    "# Space : O(1)\n",
    "\n",
    "import random\n",
    "\n",
    "nums = [1,3,5,2,7,11,15]\n",
    "target = 10\n",
    "\n",
    "# Solving with random\n",
    "def add_two_numbers(nums,target):\n",
    "    a = 0\n",
    "    b = 1\n",
    "\n",
    "    while target!=(nums[a]+nums[b]):\n",
    "        a = random.randint(0,len(nums)-1)\n",
    "        b = random.randint(0,len(nums)-1)\n",
    "        while a == b:\n",
    "            b = random.randint(0,len(nums))\n",
    "        print(f\"{nums[a]} + {nums[b]} = {target}\")\n",
    "    return a,b\n",
    "    \n",
    "add_two_numbers(nums,target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9{1: 0}\n",
      "7{1: 0, 3: 1}\n",
      "5{1: 0, 3: 1, 5: 2}\n",
      "8{1: 0, 3: 1, 5: 2, 2: 3}\n",
      "3"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(4, 1)"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Solving with hashmap single pass\n",
    "# Time  : O(n)\n",
    "# Space : O(n)\n",
    "\n",
    "nums = [1,3,5,2,7,11,15]\n",
    "target = 10\n",
    "\n",
    "# Solving with one pass using dictionary (hashmap)\n",
    "def add_two_numbers(nums,target):\n",
    "    hash_map = {}\n",
    "    for i in range(len(nums)):\n",
    "        complement = target - nums[i]         # 9 = 10 - 1\n",
    "        print(complement,end=\"\")\n",
    "        if complement in hash_map:\n",
    "            return i,hash_map[complement]\n",
    "        hash_map[nums[i]] = i # add the key (complement) <-> value (index) pair \n",
    "        print(hash_map)\n",
    "        \n",
    "add_two_numbers(nums,target)"
   ]
  }
 ],
 "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.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}