LeetCode/July LeetCoding Challenge 2020/July_LeetCoding_Challenge_2020.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Arranging Coins](https://leetcode.com/explore/featured/card/july-leetcoding-challenge/544/week-1-july-1st-july-7th/3377/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.\n",
    "\n",
    "Given n, find the total number of full staircase rows that can be formed.\n",
    "\n",
    "n is a non-negative integer and fits within the range of a 32-bit signed integer.\n",
    "\n",
    "***Example 1:***\n",
    "\n",
    "n = 5\n",
    "\n",
    "The coins can form the following rows:\\\n",
    "¤\\\n",
    "¤ ¤\\\n",
    "¤ ¤\n",
    "\n",
    "Because the 3rd row is incomplete, we return 2.\n",
    "\n",
    "***Example 2:***\n",
    "\n",
    "n = 8\n",
    "\n",
    "The coins can form the following rows:\\\n",
    "¤\\\n",
    "¤ ¤\\\n",
    "¤ ¤ ¤\\\n",
    "¤ ¤\n",
    "\n",
    "Because the 4th row is incomplete, we return 3."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 5\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def arrangeCoins(self, n: int) -> int:\n",
    "        c=0\n",
    "        while True:\n",
    "            if (2*n)<=c*(c+1) :\n",
    "                if (2*n)!=c*(c+1):\n",
    "                    c-=1\n",
    "                break\n",
    "            else:\n",
    "                c+=1\n",
    "#     print(c*(c+1))\n",
    "        return c\n",
    "print(Solution().arrangeCoins(int(input())))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Ugly Number II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***Write a program to find the n-th ugly number.***\n",
    "\n",
    "Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. \n",
    "\n",
    "**Example:**\n",
    "\n",
    "**Input:** n = 10\\\n",
    "**Output:** 12\\\n",
    "**Explanation:** 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.\\\n",
    "**Note:** \\\n",
    "1. 1 is typically treated as an ugly number.\\\n",
    "2. n does not exceed 1690."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 126\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3200\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        ugly=[0]*1690\n",
    "        ugly[0]=1\n",
    "        i2,i3,i5=[0]*3\n",
    "        next_2=2\n",
    "        next_3=3\n",
    "        next_5=5\n",
    "        for i in range(1,1690):\n",
    "            ugly[i]=min(next_2,next_3,next_5)\n",
    "            if ugly[i]==next_2:\n",
    "                i2+=1\n",
    "                next_2=ugly[i2]*2\n",
    "            if ugly[i]==next_3:\n",
    "                i3+=1\n",
    "                next_3=ugly[i3]*3\n",
    "            if ugly[i]==next_5:\n",
    "                i5+=1\n",
    "                next_5=ugly[i5]*5\n",
    "        return ugly[n-1]\n",
    "s=Solution()\n",
    "print(s.nthUglyNumber(int(input())))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#   Hamming Distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Hamming distance between two integers is the number of positions at which the corresponding bits are different.\n",
    "\n",
    "Given two integers x and y, calculate the Hamming distance.\n",
    "\n",
    "**Note:**\\\n",
    "0 ≤ x, y < 231.\n",
    "\n",
    "**Example:**\n",
    "\n",
    "**Input:** x = 1, y = 4\n",
    "\n",
    "**Output:** 2\n",
    "\n",
    "**Explanation:**\\\n",
    "1   (0 0 0 1)\\\n",
    "4   (0 1 0 0)\\\n",
    "       ↑   ↑\n",
    "\n",
    "The above arrows point to positions where the corresponding bits are different."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 1\n",
      " 4\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bin(int(input())^int(input())).count('1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "float('1_1')\n",
    "x=float(_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "11111.0"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "float('1_1_1_1_1')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Plus One\n",
    "Given a non-empty array of digits representing a non-negative integer, plus one to the integer.\n",
    "\n",
    "The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.\n",
    "\n",
    "You may assume the integer does not contain any leading zero, except the number 0 itself.\n",
    "\n",
    "**Example 1:**\n",
    "\n",
    "**Input:** [1,2,3]\\\n",
    "**Output:** [1,2,4]\\\n",
    "**Explanation:** The array represents the integer 123.\\\n",
    "**Example 2:**\n",
    "\n",
    "**Input:** [4,3,2,1]\\\n",
    "**Output:** [4,3,2,2]\\\n",
    "**Explanation:** The array represents the integer 4321."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 1 2 3\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 4]\n"
     ]
    }
   ],
   "source": [
    "a=list(map(int,input().split()))\n",
    "l=list(str(int(''.join((map(str,a))))+1))\n",
    "for i in range(len(l)):\n",
    "    l[i]=int(l[i])\n",
    "print(l)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Island Perimeter\n",
    "You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water.\n",
    "\n",
    "Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).\n",
    "\n",
    "The island doesn't have \"lakes\" (water inside that isn't connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.\n",
    "\n",
    " \n",
    "\n",
    "**Example:**\n",
    "\n",
    "**Input:**\\\n",
    "[[0,1,0,0],\\\n",
    " [1,1,1,0],\\\n",
    " [0,1,0,0],\\\n",
    " [1,1,0,0]]\n",
    "\n",
    "**Output:** 16\n",
    "\n",
    "**Explanation:** The perimeter is the 16 yellow stripes in the image below:\n",
    "\n",
    "![island](island.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def islandPerimeter(self, mat: List[List[int]]) -> int:\n",
    "        def numofneighbour(mat, i, j): \n",
    "            count = 0; \n",
    "            if (i > 0 and mat[i - 1][j]): \n",
    "                count+= 1; \n",
    "            if (j > 0 and mat[i][j - 1]): \n",
    "                count+= 1; \n",
    "            if (i < R-1 and mat[i + 1][j]): \n",
    "                count+= 1\n",
    "            if (j < C-1 and mat[i][j + 1]): \n",
    "                count+= 1; \n",
    "            return count; \n",
    "        def findperimeter(mat): \n",
    "            perimeter = 0; \n",
    "            for i in range(0, R): \n",
    "                for j in range(0, C): \n",
    "                    if (mat[i][j]): \n",
    "                        perimeter += (4 - numofneighbour(mat, i, j)); \n",
    "            return perimeter; \n",
    "        R = len(mat)\n",
    "        C = len(mat[0])\n",
    "        return(findperimeter(mat));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#   3Sum\n",
    "\n",
    "**Solution**\\\n",
    "Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.\n",
    "\n",
    "**Note:**\n",
    "\n",
    "The solution set must not contain duplicate triplets.\n",
    "\n",
    "**Example:**\n",
    "\n",
    "Given array nums = [-1, 0, 1, 2, -1, -4],\n",
    "\n",
    "A solution set is:\\\n",
    "[\\\n",
    "  [-1, 0, 1],\\\n",
    "  [-1, -1, 2]\\\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[-1, 0, 1]]\n"
     ]
    }
   ],
   "source": [
    "class Solution(object):\n",
    "    def threeSum(self, nums):\n",
    "        nums.sort()\n",
    "        result = []\n",
    "        for i in range(len(nums)-2):\n",
    "            if i> 0 and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            l = i+1\n",
    "            r = len(nums)-1\n",
    "            while(l<r):\n",
    "                sum = nums[i] + nums[l] + nums[r]\n",
    "                if sum<0:\n",
    "                    l+=1\n",
    "                elif sum >0:\n",
    "                    r-=1\n",
    "                else:\n",
    "                    result.append([nums[i],nums[l],nums[r]])\n",
    "                    while l<len(nums)-1 and nums[l] == nums[l + 1] : l += 1\n",
    "                    while r>0 and nums[r] == nums[r - 1]: r -= 1\n",
    "                    l+=1\n",
    "                    r-=1\n",
    "        return result\n",
    "ob1 = Solution()\n",
    "print(ob1.threeSum([1,-1,-1,0]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Maximum Width of Binary Tree](https://leetcode.com/explore/featured/card/july-leetcoding-challenge/545/week-2-july-8th-july-14th/3385/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.\n",
    "\n",
    "The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.\n",
    "\n",
    "**Example 1:**\n",
    "\n",
    "**Input:**\n",
    "\n",
    "           1\n",
    "         /   \\\n",
    "        3     2\n",
    "       / \\     \\  \n",
    "      5   3     9 \n",
    "\n",
    "**Output:** 4\\\n",
    "**Explanation:** The maximum width existing in the third level with the length 4 (5,3,null,9).\\\n",
    "**Example 2:**\n",
    "\n",
    "**Input:**\n",
    "\n",
    "          1\n",
    "         /  \n",
    "        3    \n",
    "       / \\       \n",
    "      5   3     \n",
    "\n",
    "**Output:** 2\\\n",
    "**Explanation:** The maximum width existing in the third level with the length 2 (5,3).\\\n",
    "**Example 3:**\n",
    "\n",
    "**Input:**\n",
    "\n",
    "          1\n",
    "         / \\\n",
    "        3   2 \n",
    "       /        \n",
    "      5      \n",
    "\n",
    "**Output:** 2\\\n",
    "**Explanation:** The maximum width existing in the second level with the length 2 (3,2).\\\n",
    "**Example 4:**\n",
    "\n",
    "**Input:**\n",
    "\n",
    "          1\n",
    "         / \\\n",
    "        3   2\n",
    "       /     \\  \n",
    "      5       9 \n",
    "     /         \\\n",
    "    6           7\n",
    "    \n",
    "**Output:** 8\\\n",
    "**Explanation:**The maximum width existing in the fourth level with the length 8 (6,null,null,null,null,null,null,7).\n",
    "\n",
    "\n",
    "**Note:** Answer will in the range of 32-bit signed integer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 6\n",
      " 20 15 24 26 4 16\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 --> 3\n",
      "15 --> 2\n",
      "16 --> 3\n",
      "20 --> 1\n",
      "24 --> 2\n",
      "26 --> 3\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self,key):\n",
    "        self.right=None\n",
    "        self.left=None\n",
    "        self.val=key\n",
    "\n",
    "def insert(root,node):\n",
    "    if root is None:\n",
    "        root=node\n",
    "    else:\n",
    "        if root.val<node.val:\n",
    "            if root.right is None:\n",
    "                root.right=node\n",
    "            else:\n",
    "                insert(root.right,node)\n",
    "        else:\n",
    "            if root.left is None:\n",
    "                root.left=node\n",
    "            else:\n",
    "                insert(root.left,node)\n",
    "h=0\n",
    "l1=[]\n",
    "\n",
    "def inorder(root,h):\n",
    "    if root:\n",
    "        inorder(root.left,h+1)\n",
    "        print(root.val,h,sep=' --> ')\n",
    "        l1.append(h)\n",
    "        inorder(root.right,h+1)\n",
    "\n",
    "n=int(input())\n",
    "a=list(map(int,input().split()))\n",
    "for i in range(n):\n",
    "    if i==0:\n",
    "        r=Node(a[i])\n",
    "    else:\n",
    "        insert(r,Node(a[i]))\n",
    "inorder(r,1)\n",
    "print(l1.count(max(l1))*2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def widthOfBinaryTree(self, root: TreeNode) -> int:\n",
    "        if root is None: return 0\n",
    "        result=1\n",
    "        Queue=[[root,0]]\n",
    "        while len(Queue)>0:\n",
    "            count=len(Queue)\n",
    "            start=Queue[0][1]\n",
    "            end=Queue[-1][0]\n",
    "            result=max(result,end-start+1)\n",
    "            for i in range(count):\n",
    "                p=Queue[0]\n",
    "                idx=p[1]-satrt\n",
    "                Queue.pop()\n",
    "                if p[0].left: Queue.append([p[0].left,2*idx+1])\n",
    "                if p[0].right: Queue.append([p[0].right,2*idx+2])\n",
    "            return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Subsets](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge/545/week-2-july-8th-july-14th/3387/)\n",
    "\n",
    "<pre>\n",
    "Given a set of distinct integers, nums, return all possible subsets (the power set).\n",
    "\n",
    "Note: The solution set must not contain duplicate subsets.\n",
    "\n",
    "<b>Example:</b>\n",
    "\n",
    "<b>Input:</b> nums = [1,2,3]\n",
    "<b>Output:</b>\n",
    "[\n",
    "  [3],\n",
    "  [1],\n",
    "  [2],\n",
    "  [1,2,3],\n",
    "  [1,3],\n",
    "  [2,3],\n",
    "  [1,2],\n",
    "  []\n",
    "]\n",
    "</pre>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 1 2 3 4\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 2, 3, 4]]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[[1, 2, 3, 4],\n",
       " [4],\n",
       " [1, 2, 3],\n",
       " [1, 4],\n",
       " [2, 4],\n",
       " [3, 4],\n",
       " [3],\n",
       " [1, 2],\n",
       " [1, 3],\n",
       " [2, 3],\n",
       " [2],\n",
       " [1],\n",
       " []]"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "l=[]\n",
    "a=list(map(int,input().split()))\n",
    "l.append(a.copy())\n",
    "print(l)\n",
    "while a:\n",
    "    k=a.pop()\n",
    "    if [k] not in l:\n",
    "        l.append([k])\n",
    "    if a not in l:\n",
    "        l.append(a.copy())\n",
    "    for i in a:\n",
    "        if [i,k] not in l:\n",
    "            l.append([i,k])\n",
    "l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 1 2 3\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[[]], [[1], [2], [3]], [[1, 2], [1, 3], [2, 3]], [[1, 2, 3]]]\n"
     ]
    }
   ],
   "source": [
    "import itertools as it\n",
    "def combinations_all(l,i):\n",
    "    return list(map(list, itertools.combinations(l, i)))\n",
    "    \n",
    "\n",
    "a=list(map(int,input().split()))\n",
    "l=[]\n",
    "for i in range(len(a)+1):\n",
    "    l.append(combinations_all(a,i))\n",
    "print(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[], [4], [3], [3, 4], [2], [2, 4], [2, 3], [2, 3, 4], [1], [1, 4], [1, 3], [1, 3, 4], [1, 2], [1, 2, 4], [1, 2, 3], [1, 2, 3, 4]]\n"
     ]
    }
   ],
   "source": [
    "class Solution(object):\n",
    "    def subsets(self, nums):\n",
    "        temp_result = []\n",
    "        self.subsets_util(nums,[0 for i in range(len(nums))],temp_result,0)\n",
    "        main_result = []\n",
    "        for lists in temp_result:\n",
    "            temp = []\n",
    "            for i in range(len(lists)):\n",
    "                if lists[i] == 1:\n",
    "                    temp.append(nums[i])\n",
    "            main_result.append(temp)\n",
    "        return main_result\n",
    "    def subsets_util(self,nums,temp,result,index):\n",
    "        if index == len(nums):\n",
    "            result.append([i for i in temp])\n",
    "         #print(temp)\n",
    "            return\n",
    "        temp[index] = 0\n",
    "        self.subsets_util(nums,temp,result,index+1)\n",
    "        temp[index] = 1\n",
    "        self.subsets_util(nums, temp, result,index + 1)\n",
    "ob1 = Solution()\n",
    "print(ob1.subsets([1,2,3,4]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Reverse Bits](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge/545/week-2-july-8th-july-14th/3388/)\n",
    "\n",
    "<pre>\n",
    "Reverse bits of a given 32 bits unsigned integer.\n",
    "\n",
    " \n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: 00000010100101000001111010011100\n",
    "Output: 00111001011110000010100101000000\n",
    "Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.\n",
    "Example 2:\n",
    "\n",
    "Input: 11111111111111111111111111111101\n",
    "Output: 10111111111111111111111111111111\n",
    "Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.\n",
    " \n",
    "\n",
    "Note:\n",
    "\n",
    "Note that in some languages such as Java, there is no unsigned integer type. In this case, both input and output will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.\n",
    "In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 2 above the input represents the signed integer -3 and the output represents the signed integer -1073741825.\n",
    " \n",
    "\n",
    "Follow up:\n",
    "\n",
    "If this function is called many times, how would you optimize it?\n",
    "</pre>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 2\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "1073741824"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x=bin(int(input()))[2:]\n",
    "int(('0'*(32-len(x))+x)[::-1],2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 2\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1073741824\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def reverseBits(self, n: int) -> int:\n",
    "        x=bin(n)[2:]\n",
    "        return int(('0'*(32-len(x))+x)[::-1],2)\n",
    "print(Solution().reverseBits(int(input())))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# WEEK 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [Reverse Words in a String](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge/546/week-3-july-15th-july-21st/3391/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " thw lwad jjhj kjj\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'kjj jjhj lwad thw'"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s=input()\n",
    "' '.join(s.strip().split()[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " \"  hello world!  \"\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\" world! hello \"\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def reverseWords(self, s: str) -> str:\n",
    "        return ' '.join(s.strip().split()[::-1])\n",
    "print(Solution().reverseWords(input()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [  Pow(x, n)](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge/546/week-3-july-15th-july-21st/3392/)\n",
    "\n",
    "<pre>\n",
    "Implement pow(x, n), which calculates x raised to the power n (xn).\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: 2.00000, 10\n",
    "Output: 1024.00000\n",
    "Example 2:\n",
    "\n",
    "Input: 2.10000, 3\n",
    "Output: 9.26100\n",
    "Example 3:\n",
    "\n",
    "Input: 2.00000, -2\n",
    "Output: 0.25000\n",
    "Explanation: 2-2 = 1/22 = 1/4 = 0.25\n",
    "Note:\n",
    "\n",
    "-100.0 < x < 100.0\n",
    "n is a 32-bit signed integer, within the range [−231, 231 − 1]\n",
    "</pre>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1024.0"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2.00000**10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###   [Add Binary](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge/546/week-3-july-15th-july-21st/3395/)\n",
    "\n",
    "<pre>\n",
    "Given two binary strings, return their sum (also a binary string).\n",
    "\n",
    "The input strings are both non-empty and contains only characters 1 or 0.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: a = \"11\", b = \"1\"\n",
    "Output: \"100\"\n",
    "Example 2:\n",
    "\n",
    "Input: a = \"1010\", b = \"1011\"\n",
    "Output: \"10101\"\n",
    " \n",
    "\n",
    "Constraints:\n",
    "\n",
    "Each string consists only of '0' or '1' characters.\n",
    "1 <= a.length, b.length <= 10^4\n",
    "Each string is either \"0\" or doesn't contain any leading zero.\n",
    "</pre>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'10101'"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bin(int('1010',2)+int('1011',2))[2:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [  Remove Linked List Elements](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge/546/week-3-july-15th-july-21st/3396/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 4\n",
      " 2\n",
      " 5\n",
      " 2\n",
      " 7\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 5 2 7 "
     ]
    }
   ],
   "source": [
    "class node:\n",
    "    def __init__(self,val):\n",
    "        self.data=val\n",
    "        self.next=None\n",
    "class LinkedList:\n",
    "    def __init__(self):\n",
    "        self.start=None\n",
    "    def add_data(self):\n",
    "        for i in range(int(input())):\n",
    "            if self.start is None:\n",
    "                self.start=node(int(input()))\n",
    "                ptr=self.start\n",
    "            else:\n",
    "                ptr.next=node(int(input()))\n",
    "                ptr=ptr.next\n",
    "        return self.start\n",
    "    def display(self,head):\n",
    "        ptr=head\n",
    "        while ptr:\n",
    "            print(ptr.data,end=' ')\n",
    "            ptr=ptr.next\n",
    "\n",
    "l=LinkedList()\n",
    "head=l.add_data()\n",
    "l.display(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 2\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 7 "
     ]
    }
   ],
   "source": [
    "def remove_data(root):\n",
    "    data=int(input())\n",
    "    l=LinkedList()\n",
    "    while root:\n",
    "        if root.data!=data:\n",
    "            if l.start is None:\n",
    "                l.start=node(root.data)\n",
    "                ptr=l.start\n",
    "            else:              \n",
    "                ptr.next=node(root.data)\n",
    "                ptr=ptr.next\n",
    "        root=root.next\n",
    "    return l.start\n",
    "head1=remove_data(head)\n",
    "l.display(head1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 5 2 7 "
     ]
    }
   ],
   "source": [
    "l.display(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "def getNode(head, p):\n",
    "    l=[]\n",
    "    while head:\n",
    "        l.append(head.data)\n",
    "        head=head.next\n",
    "    return l[-p-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "getNode(head,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "def getNode(head, p):\n",
    "    tracked=head\n",
    "    while head:\n",
    "        if p>-1:\n",
    "            p-=1\n",
    "        else:\n",
    "            tracked=tracked.next\n",
    "        head=head.next\n",
    "    return tracked.data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "def has_cycle(head):\n",
    "    l=[]\n",
    "    while head:\n",
    "        if head.data in l:\n",
    "            return True\n",
    "        else:\n",
    "            l.append(head.data)\n",
    "            head=head.next\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "has_cycle(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "has_cycle(head1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [Climbing Stairs](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge/548/week-5-july-29th-july-31st/3407/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 4\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "n=int(input())\n",
    "c_2=n//2\n",
    "c_1=n%2\n",
    "sum_p=1\n",
    "while c_2:\n",
    "    sum_p+=get_p(c_2+c_1,c_2,c_1)\n",
    "    c_2-=1\n",
    "    c_1+=2\n",
    "print(sum_p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fact(n):\n",
    "    if n==0:\n",
    "        return 1\n",
    "    return n*fact(n-1)\n",
    "def get_p(n,n1,n2):\n",
    "    return fact(n)//(fact(n1)*fact(n2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "24"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fact(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_p(3,1,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "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.8.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}