30th_Dec_DSA_Assignment.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "422007d9",
   "metadata": {},
   "source": [
    "# DSA\n",
    "## Assignment Questions"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cf01492a",
   "metadata": {},
   "source": [
    "# Problem 1: Reverse a singly linked list.\n",
    "    \n",
    "<b>Input: 1 -> 2 -> 3 -> 4 -> 5</b>\n",
    "\n",
    "<b>Output: 5 -> 4 -> 3 -> 2 -> 1</b>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "60c64b08",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-02-27T05:00:27.738588Z",
     "start_time": "2024-02-27T05:00:27.717130Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original linked-list:\n",
      "1-->2-->3-->4-->5-->None\n",
      "\n",
      "reversed linked list:\n",
      "5-->4-->3-->2-->1-->None\n"
     ]
    }
   ],
   "source": [
    "# Defining the class Node\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, data = None, next = None):\n",
    "        self.data = data\n",
    "        self.next = next\n",
    "    # Method to set the data \n",
    "    def setdata(self,data):\n",
    "        self.data = data\n",
    "    # Method to get the data\n",
    "    def getdata(self):\n",
    "        return self.data\n",
    "    #Method to set the next\n",
    "    def setnext(self,next):\n",
    "        self.next = next\n",
    "    #Method to get the next\n",
    "    def getnext(self):\n",
    "        return self.next\n",
    "\n",
    "# creating the nodes\n",
    "\n",
    "head = Node(1)\n",
    "node2 = Node(2)\n",
    "node3 = Node(3)\n",
    "node4 = Node(4)\n",
    "node5 = Node(5)\n",
    "\n",
    "# linking the nodes/ creating the linked list\n",
    "\n",
    "head.setnext(node2)\n",
    "node2.setnext(node3)\n",
    "node3.setnext(node4)\n",
    "node4.setnext(node5)\n",
    "\n",
    "#Function to traverse through the linked list\n",
    "\n",
    "def traverse(head):\n",
    "    temp = head\n",
    "    while(temp):\n",
    "        print(temp.getdata(),end = \"-->\")\n",
    "        temp = temp.getnext()\n",
    "    print(\"None\")\n",
    "\n",
    "#Function to reverse the order of linked list\n",
    "\n",
    "def reverse_linkedlist(head):\n",
    "    prev = None\n",
    "    current = head\n",
    "    while current:\n",
    "        next_node = current.getnext()\n",
    "        current.setnext(prev)\n",
    "        prev = current \n",
    "        current = next_node\n",
    "    return prev\n",
    "\n",
    "print(\"Original linked-list:\")\n",
    "traverse(head)\n",
    "print()\n",
    "new_head = reverse_linkedlist(head)\n",
    "print(\"reversed linked list:\")\n",
    "traverse(new_head)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "37d1d45e",
   "metadata": {},
   "source": [
    "# Problem 2: Merge two sorted linked lists into one sorted linked list\n",
    "## Input: List 1: 1 -> 3 -> 5, List 2: 2 -> 4 -> 6\n",
    "\n",
    "## Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "27c0c96f",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-02-27T05:00:29.862532Z",
     "start_time": "2024-02-27T05:00:29.849510Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1-->3-->5-->None\n",
      "2-->4-->6-->None\n",
      "1-->2-->3-->4-->5-->6-->None\n"
     ]
    }
   ],
   "source": [
    "#creating nodes of  linked list L1 ------\n",
    "head_a = Node(1)\n",
    "node_a1 = Node(3)\n",
    "node_a2 = Node(5)\n",
    "\n",
    "# linking the nodes of L1--------\n",
    "head_a.setnext(node_a1)\n",
    "node_a1.setnext(node_a2)\n",
    "\n",
    "#creating linked list L2 ------\n",
    "head_b = Node(2)\n",
    "node_b1 = Node(4)\n",
    "node_b2 = Node(6)\n",
    "\n",
    "# linking the nodes of L2--------\n",
    "head_b.setnext(node_b1)\n",
    "node_b1.setnext(node_b2)\n",
    "\n",
    "traverse(head_a)\n",
    "traverse(head_b)\n",
    "\n",
    "#Merging two sorted linked lists into one sorted linked list\n",
    "\n",
    "def merge_sorted_LL(head_a, head_b):\n",
    "    temp = Node()\n",
    "    current = temp\n",
    "    while(head_a and head_b):\n",
    "        if head_a.getdata() >= head_b.getdata():\n",
    "            current.setnext(Node(head_b.getdata()))\n",
    "            head_b = head_b.getnext()\n",
    "        else:\n",
    "            current.setnext(Node(head_a.getdata()))\n",
    "            head_a = head_a.getnext()\n",
    "        current = current.getnext()\n",
    "        \n",
    "    if head_a:\n",
    "        current.setnext(head_a)\n",
    "    if head_b:\n",
    "        current.setnext(head_b)\n",
    "    \n",
    "    return temp.getnext()\n",
    "\n",
    "new_head = merge_sorted_LL(head_a, head_b)\n",
    "traverse(new_head)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "90b6330d",
   "metadata": {},
   "source": [
    "# Problem 3: Remove the nth node from the end of a linked list.\n",
    "\n",
    "## Input: 1 -> 2 -> 3 -> 4 -> 5, n = 2\n",
    "\n",
    "## Output: 1 -> 2 -> 3 -> 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "4705757b",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-02-27T05:00:31.436650Z",
     "start_time": "2024-02-27T05:00:30.649484Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original linked list:\n",
      "1-->2-->3-->4-->5-->None\n",
      "\n",
      "Enter the position of the node to be deleted from the end:2\n",
      "\n",
      "After deletion of the 2th element from the end:\n",
      "1-->2-->3-->5-->None\n"
     ]
    }
   ],
   "source": [
    "# creating the nodes\n",
    "\n",
    "head = Node(1)\n",
    "node2 = Node(2)\n",
    "node3 = Node(3)\n",
    "node4 = Node(4)\n",
    "node5 = Node(5)\n",
    "\n",
    "# linking the nodes/ creating the linked list\n",
    "\n",
    "head.setnext(node2)\n",
    "node2.setnext(node3)\n",
    "node3.setnext(node4)\n",
    "node4.setnext(node5)\n",
    "\n",
    "#function to check the length of the linked list\n",
    "def length(head):\n",
    "    temp = head\n",
    "    c = 0\n",
    "    while temp:\n",
    "        c += 1\n",
    "        temp = temp.getnext()\n",
    "    return c\n",
    "\n",
    "\n",
    "# Function to delete the nth node from the end of the linked list\n",
    "def delete_node_end(head,n):\n",
    "    k = length(head) - n #n-th node from the end is k-th node from the front\n",
    "    if k >= length(head) or k < 0 or not head:\n",
    "        print(\"Enter valid value of n\")\n",
    "        return head\n",
    "    if k == 0:\n",
    "        head = head.getnext()\n",
    "    else:\n",
    "        #we jump to k-1`th position \n",
    "        i = 0\n",
    "        prev = head\n",
    "        while(i<k-1):\n",
    "            prev = prev.getnext()\n",
    "            i+=1\n",
    "        #prev will be pointing to the node left of the k`th position\n",
    "        prev.setnext(prev.getnext().getnext())\n",
    "        \n",
    "    return head\n",
    "    \n",
    "        \n",
    "        \n",
    "print(\"Original linked list:\")\n",
    "traverse(head)\n",
    "print()\n",
    "n = int(input(\"Enter the position of the node to be deleted from the end:\"))\n",
    "new_head = delete_node_end(head,n)\n",
    "print()\n",
    "print(f\"After deletion of the {n}th element from the end:\")\n",
    "traverse(new_head)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "01d8b457",
   "metadata": {},
   "source": [
    "# Problem 4: Find the intersection point of two linked lists.\n",
    "## Input: List 1: 1 -> 2 -> 3 -> 4, List 2: 9 -> 8 -> 3 -> 4\n",
    "\n",
    "## Output: Node with value 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "84a96cff",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1-->2-->3-->4-->None\n",
      "\n",
      "9-->8-->3-->4-->None\n",
      "\n",
      "Intersection point of the two linked list is : 3\n"
     ]
    }
   ],
   "source": [
    "# List-1 is defined here\n",
    "\n",
    "head11 =Node(1)\n",
    "node2 =Node(2)\n",
    "node3 =Node(3)\n",
    "node4 =Node(4)\n",
    "\n",
    "# Create Linkage of nodes\n",
    "head11.setnext(node2)\n",
    "node2.setnext(node3)\n",
    "node3.setnext(node4)\n",
    "\n",
    "# list-2 is define\n",
    "head21 =Node(9)\n",
    "node8 =Node(8)\n",
    "node3 =Node(3)\n",
    "node4 =Node(4)\n",
    "\n",
    "# create linkage of nodes\n",
    "head21.setnext(node8)\n",
    "node8.setnext(node3)\n",
    "node3.setnext(node4)\n",
    "traverse(head11)\n",
    "print()\n",
    "traverse(head21)\n",
    "print()\n",
    "def IntersectPoint(head11 ,head21):\n",
    "    temp1 =head11\n",
    "    temp2 =head21\n",
    "    while(temp1 and temp2):\n",
    "        if(temp1.getdata() == temp2.getdata()):\n",
    "            return temp1.getdata()\n",
    "        temp1 =temp1.getnext()\n",
    "        temp2 =temp2.getnext()\n",
    "\n",
    "print(\"Intersection point of the two linked list is :\",IntersectPoint(head11 ,head21))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2294f206",
   "metadata": {},
   "source": [
    "# Problem 5: Remove duplicates from a sorted linked list.\n",
    "\n",
    "## Input: 1 -> 1 -> 2 -> 3 -> 3\n",
    "## Output: 1 -> 2 -> 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "7d2d4800",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original linkedlist:\n",
      "\n",
      "1-->2-->3-->3-->None\n",
      "\n",
      "After removing duplicates:\n",
      "\n",
      "1-->2-->3-->None\n"
     ]
    }
   ],
   "source": [
    "# creating the nodes\n",
    "head = Node(1)\n",
    "node2 = Node(2)\n",
    "node3 = Node(3)\n",
    "node4 = Node(3)\n",
    "\n",
    "#creating linkage\n",
    "head.setnext(node2)\n",
    "node2.setnext(node3)\n",
    "node3.setnext(node4)\n",
    "\n",
    "def remove_duplicates(head):\n",
    "    temp = head\n",
    "    while(temp and temp.getnext()):\n",
    "        if temp.getdata() == temp.getnext().getdata():\n",
    "            temp.setnext(temp.getnext().getnext())\n",
    "        else:\n",
    "            temp = temp.getnext()\n",
    "    \n",
    "print(\"Original linkedlist:\\n\")\n",
    "traverse(head)\n",
    "remove_duplicates(head)\n",
    "print(\"\\nAfter removing duplicates:\\n\")\n",
    "traverse(head)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "422180b0",
   "metadata": {},
   "source": [
    "# Problem 6: Add two numbers represented by linked lists (where each node contains a single digit)\n",
    "\n",
    "## Input: List 1: 2 -> 4 -> 3, List 2: 5 -> 6 -> 4 (represents 342 + 465)\n",
    "\n",
    "## Output: 7 -> 0 -> 8 (represents 807)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "3fbf33fb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "List1:\n",
      "2-->4-->3-->None\n",
      "\n",
      "List2:\n",
      "5-->6-->4-->None\n",
      "\n",
      "After adding:\n",
      "7-->0-->8-->None\n"
     ]
    }
   ],
   "source": [
    "# List 1\n",
    "head1 = Node(2)\n",
    "node12 = Node(4)\n",
    "node13 = Node(3)\n",
    "#connecting the nodes\n",
    "head1.setnext(node12)\n",
    "node12.setnext(node13)\n",
    "#list 2\n",
    "head2 = Node(5)\n",
    "node22 = Node(6)\n",
    "node23 = Node(4)\n",
    "#connecting the nodes\n",
    "head2.setnext(node22)\n",
    "node22.setnext(node23)\n",
    "\n",
    "\n",
    "\n",
    "def add_two_numbers(head1, head2):\n",
    "    l1,l2 = head1,head2\n",
    "    dummy_head = Node()\n",
    "    current = dummy_head\n",
    "    carry = 0\n",
    "\n",
    "    while l1 or l2 or carry:\n",
    "        sum_val = carry\n",
    "        if l1:\n",
    "            sum_val += l1.getdata()\n",
    "            l1 = l1.getnext()\n",
    "        if l2:\n",
    "            sum_val += l2.getdata()\n",
    "            l2 = l2.getnext()\n",
    "        \n",
    "        carry, digit = divmod(sum_val, 10)\n",
    "        current.setnext(Node(digit))  \n",
    "        current = current.getnext()\n",
    "\n",
    "    return dummy_head.getnext()\n",
    "\n",
    "print(\"List1:\")\n",
    "traverse(head1)\n",
    "print(\"\\nList2:\")\n",
    "traverse(head2)\n",
    "k = add_two_numbers(head1,head2)\n",
    "print(\"\\nAfter adding:\")\n",
    "traverse(k)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5ba35de2",
   "metadata": {},
   "source": [
    "# Problem 7: Swap nodes in pairs in a linked list.\n",
    "\n",
    "## Input: 1 -> 2 -> 3 -> 4\n",
    "\n",
    "## Output: 2 -> 1 -> 4 -> 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "a91eea47",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original list:\n",
      "1-->2-->3-->4-->None\n",
      "After swapping:\n",
      "2-->1-->4-->3-->None\n"
     ]
    }
   ],
   "source": [
    "# creating the nodes\n",
    "\n",
    "head = Node(1)\n",
    "node2 = Node(2)\n",
    "node3 = Node(3)\n",
    "node4 = Node(4)\n",
    "\n",
    "# linking the nodes/ creating the linked list\n",
    "\n",
    "head.setnext(node2)\n",
    "node2.setnext(node3)\n",
    "node3.setnext(node4)\n",
    "\n",
    "def swap_nodes(head):\n",
    "    prev = dummy_node = Node()\n",
    "    while(head and head.getnext()):\n",
    "        firstnode = head\n",
    "        secondnode = head.getnext()\n",
    "        \n",
    "        #swapping the nodes\n",
    "        prev.setnext(secondnode)\n",
    "        firstnode.setnext(secondnode.getnext())\n",
    "        secondnode.setnext(firstnode)\n",
    "        \n",
    "        #moving the pointers\n",
    "        prev = firstnode\n",
    "        head = firstnode.getnext()\n",
    "    return dummy_node.getnext()\n",
    "\n",
    "print(\"Original list:\")\n",
    "traverse(head)\n",
    "new_node = swap_nodes(head)\n",
    "print(\"After swapping:\")\n",
    "traverse(new_node)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eaa07401",
   "metadata": {},
   "source": [
    "# Problem 8: Reverse nodes in a linked list in groups of k\n",
    "\n",
    "## Input: 1 -> 2 -> 3 -> 4 -> 5, k = 3\n",
    "\n",
    "## Output: 3 -> 2 -> 1 -> 4 -> 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "2746dd0a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original Linked list:\n",
      "1-->2-->3-->4-->5-->None\n",
      "Output:\n",
      "3-->2-->1-->4-->5-->None\n"
     ]
    }
   ],
   "source": [
    "def reverse_k_group(head, k):\n",
    "    if not head or k == 1:\n",
    "        return head\n",
    "\n",
    "    dummy = Node(0)\n",
    "    dummy.setnext(head)\n",
    "    prev_group_end = dummy\n",
    "\n",
    "    while prev_group_end:\n",
    "        group_start = prev_group_end.getnext()\n",
    "        group_end = group_start\n",
    "        for _ in range(k - 1):\n",
    "            group_end = group_end.getnext()\n",
    "            if not group_end:\n",
    "                return dummy.getnext()\n",
    "\n",
    "        next_group_start = group_end.getnext()\n",
    "        group_end.setnext(None)\n",
    "\n",
    "        # Reverse the current group\n",
    "        prev = None\n",
    "        current = group_start\n",
    "        while current:\n",
    "            next_node = current.getnext()\n",
    "            current.setnext(prev)\n",
    "            prev = current\n",
    "            current = next_node\n",
    "\n",
    "        # Connect the reversed group back to the main list\n",
    "        prev_group_end.setnext(group_end)\n",
    "        group_start.setnext(next_group_start)\n",
    "\n",
    "        # Update prev_group_end for the next iteration\n",
    "        prev_group_end = group_start\n",
    "\n",
    "    return dummy.getnext()\n",
    "\n",
    "# creating the nodes\n",
    "\n",
    "head = Node(1)\n",
    "node2 = Node(2)\n",
    "node3 = Node(3)\n",
    "node4 = Node(4)\n",
    "node5 = Node(5)\n",
    "\n",
    "# linking the nodes/ creating the linked list\n",
    "\n",
    "head.setnext(node2)\n",
    "node2.setnext(node3)\n",
    "node3.setnext(node4)\n",
    "node4.setnext(node5)\n",
    "\n",
    "print(\"Original Linked list:\")\n",
    "traverse(head)\n",
    "new_head = reverse_k_group(head,3)\n",
    "print(\"Output:\")\n",
    "traverse(new_head)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5438017c",
   "metadata": {},
   "source": [
    "# Problem 9: Determine if a linked list is a palindrome.\n",
    "\n",
    "## Input: 1 -> 2 -> 2 -> 1\n",
    "## Output: True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "c5c379b6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Linked list:\n",
      "1-->2-->2-->1-->None\n",
      "Is palindrome? True\n"
     ]
    }
   ],
   "source": [
    "def is_palindrome(head):\n",
    "    if not head or not head.getnext():\n",
    "        return True\n",
    "\n",
    "    # Find the middle of the linked list\n",
    "    slow = head\n",
    "    fast = head\n",
    "    while fast.getnext() and fast.getnext().getnext():\n",
    "        slow = slow.getnext()\n",
    "        fast = fast.getnext().getnext()\n",
    "\n",
    "    # Reverse the second half of the linked list\n",
    "    second_half_head = reverse_linked_list(slow.getnext())\n",
    "\n",
    "    # Compare the first half with the reversed second half\n",
    "    first_half = head\n",
    "    second_half = second_half_head\n",
    "    while second_half:\n",
    "        if first_half.getdata() != second_half.getdata():\n",
    "            return False\n",
    "        first_half = first_half.getnext()\n",
    "        second_half = second_half.getnext()\n",
    "\n",
    "    return True\n",
    "\n",
    "def reverse_linked_list(head):\n",
    "    prev = None\n",
    "    current = head\n",
    "    while current:\n",
    "        next_node = current.getnext()\n",
    "        current.setnext(prev)\n",
    "        prev = current\n",
    "        current = next_node\n",
    "    return prev\n",
    "\n",
    "# Creating a linked list\n",
    "head = Node(1)\n",
    "node2 = Node(2)\n",
    "node3 = Node(2)\n",
    "node4 = Node(1)\n",
    "\n",
    "# Linking the nodes\n",
    "head.setnext(node2)\n",
    "node2.setnext(node3)\n",
    "node3.setnext(node4)\n",
    "\n",
    "# Traversing and printing the linked list\n",
    "print(\"Linked list:\")\n",
    "traverse(head)\n",
    "\n",
    "# Checking if the linked list is a palindrome\n",
    "print(\"Is palindrome?\", is_palindrome(head))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "32114cb1",
   "metadata": {},
   "source": [
    "# Problem 10: Rotate a linked list to the right by k places.\n",
    "\n",
    "## Input: 1 -> 2 -> 3 -> 4 -> 5, k = 2\n",
    "## Output: 4 -> 5 -> 1 -> 2 -> 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "f52cbddf",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original Linked list:\n",
      "1-->2-->3-->4-->5-->None\n",
      "Output:\n",
      "4-->5-->1-->2-->3-->None\n"
     ]
    }
   ],
   "source": [
    "def rotate_right(head, k):\n",
    "    if not head or k == 0:\n",
    "        return head\n",
    "\n",
    "    # Find the length of the linked list\n",
    "    length = 1\n",
    "    tail = head\n",
    "    while tail.getnext():\n",
    "        tail = tail.getnext()\n",
    "        length += 1\n",
    "\n",
    "    # Calculate the actual number of rotations needed\n",
    "    k %= length\n",
    "    if k == 0:\n",
    "        return head\n",
    "\n",
    "    # Traverse to the (length - k) - 1 node\n",
    "    prev = head\n",
    "    for _ in range(length - k - 1):\n",
    "        prev = prev.getnext()\n",
    "\n",
    "    # Set the new head and break the list\n",
    "    new_head = prev.getnext()\n",
    "    prev.setnext(None)\n",
    "\n",
    "    # Connect the tail to the original head\n",
    "    tail.setnext(head)\n",
    "\n",
    "    return new_head\n",
    "\n",
    "# creating the nodes\n",
    "\n",
    "head = Node(1)\n",
    "node2 = Node(2)\n",
    "node3 = Node(3)\n",
    "node4 = Node(4)\n",
    "node5 = Node(5)\n",
    "\n",
    "# linking the nodes/ creating the linked list\n",
    "\n",
    "head.setnext(node2)\n",
    "node2.setnext(node3)\n",
    "node3.setnext(node4)\n",
    "node4.setnext(node5)\n",
    "\n",
    "print(\"Original Linked list:\")\n",
    "traverse(head)\n",
    "new_head = rotate_right(head,2)\n",
    "print(\"Output:\")\n",
    "traverse(new_head)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7829bf7a",
   "metadata": {},
   "source": [
    "# Problem 11: Flatten a multilevel doubly linked list.\n",
    "## Input: 1 <-> 2 <-> 3 <-> 7 <-> 8 <-> 11 -> 12, 4 <-> 5 -> 9 -> 10, 6 -> 13\n",
    "## Output: 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> 6 <-> 7 <-> 8 <-> 9 <-> 10 <-> 11 <-> 12 <-> 13"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "6c4ceefe",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Flattened list:\n",
      "1 <-> 2 <-> 3 <-> 4 <-> 7 <-> 8 <-> 11 <-> 12 <-> None\n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self, val=None, prev=None, next=None, child=None):\n",
    "        self.val = val\n",
    "        self.prev = prev\n",
    "        self.next = next\n",
    "        self.child = child\n",
    "\n",
    "def flatten(head):\n",
    "    if not head:\n",
    "        return None\n",
    "\n",
    "    current = head\n",
    "    while current:\n",
    "        if current.child:\n",
    "            next_node = current.next\n",
    "            child_tail = flatten(current.child)\n",
    "            current.next = current.child\n",
    "            current.child.prev = current\n",
    "            current.child = None\n",
    "            if next_node:\n",
    "                child_tail.next = next_node\n",
    "                next_node.prev = child_tail\n",
    "            current = child_tail\n",
    "        else:\n",
    "            current = current.next\n",
    "\n",
    "    return head\n",
    "\n",
    "def print_list(head):\n",
    "    current = head\n",
    "    while current:\n",
    "        print(current.val, end=\" <-> \")\n",
    "        current = current.next\n",
    "    print(\"None\")\n",
    "\n",
    "# Create the input multilevel doubly linked list\n",
    "# Level 1\n",
    "head = Node(1)\n",
    "node2 = Node(2)\n",
    "node3 = Node(3)\n",
    "node7 = Node(7)\n",
    "node8 = Node(8)\n",
    "node11 = Node(11)\n",
    "node12 = Node(12)\n",
    "# Level 2\n",
    "node4 = Node(4)\n",
    "node5 = Node(5)\n",
    "node9 = Node(9)\n",
    "node10 = Node(10)\n",
    "# Level 3\n",
    "node6 = Node(6)\n",
    "node13 = Node(13)\n",
    "\n",
    "# Connect the nodes\n",
    "head.next = node2\n",
    "node2.prev = head\n",
    "node2.next = node3\n",
    "node3.prev = node2\n",
    "node3.next = node7\n",
    "node7.prev = node3\n",
    "node7.next = node8\n",
    "node8.prev = node7\n",
    "node8.next = node11\n",
    "node11.prev = node8\n",
    "node11.next = node12\n",
    "node12.prev = node11\n",
    "\n",
    "node3.child = node4\n",
    "node4.next = node5\n",
    "node5.prev = node4\n",
    "node5.next = node9\n",
    "node9.prev = node5\n",
    "node9.next = node10\n",
    "node10.prev = node9\n",
    "\n",
    "node9.child = node6\n",
    "node6.next = node13\n",
    "node13.prev = node6\n",
    "\n",
    "# Flatten the list\n",
    "head = flatten(head)\n",
    "\n",
    "# Print the flattened list\n",
    "print(\"Flattened list:\")\n",
    "print_list(head)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d15130ae",
   "metadata": {},
   "source": [
    "# Problem 12: Rearrange a linked list such that all even positioned nodes are placed at the end\n",
    "## Input: 1 -> 2 -> 3 -> 4 -> 5\n",
    "\n",
    "## Output: 1 -> 3 -> 5 -> 2 -> 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "6f899684",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original linked list:\n",
      "1 -> 2 -> 3 -> 4 -> 5 -> None\n",
      "Rearranged linked list:\n",
      "1 -> 3 -> 5 -> 2 -> 4 -> None\n"
     ]
    }
   ],
   "source": [
    "# Defining the class Node\n",
    "class Node:\n",
    "    def __init__(self, data=None, next=None):\n",
    "        self.data = data\n",
    "        self.next = next\n",
    "\n",
    "    # Method to set the data \n",
    "    def setdata(self, data):\n",
    "        self.data = data\n",
    "\n",
    "    # Method to get the data\n",
    "    def getdata(self):\n",
    "        return self.data\n",
    "\n",
    "    # Method to set the next\n",
    "    def setnext(self, next):\n",
    "        self.next = next\n",
    "\n",
    "    # Method to get the next\n",
    "    def getnext(self):\n",
    "        return self.next\n",
    "\n",
    "# Function to traverse through the linked list\n",
    "def traverse(head):\n",
    "    temp = head\n",
    "    while temp:\n",
    "        print(temp.getdata(), end=\" -> \")\n",
    "        temp = temp.getnext()\n",
    "    print(\"None\")\n",
    "\n",
    "def rearrange_linked_list(head):\n",
    "    if not head or not head.getnext():\n",
    "        return head\n",
    "\n",
    "    # Separate the linked list into two lists: odd-positioned and even-positioned nodes\n",
    "    odd_head = Node()\n",
    "    even_head = Node()\n",
    "    odd_tail = odd_head\n",
    "    even_tail = even_head\n",
    "    is_odd = True\n",
    "    current = head\n",
    "    while current:\n",
    "        if is_odd:\n",
    "            odd_tail.setnext(current)\n",
    "            odd_tail = odd_tail.getnext()\n",
    "        else:\n",
    "            even_tail.setnext(current)\n",
    "            even_tail = even_tail.getnext()\n",
    "        is_odd = not is_odd\n",
    "        current = current.getnext()\n",
    "\n",
    "    # Connect the odd-positioned nodes list with the even-positioned nodes list\n",
    "    odd_tail.setnext(even_head.getnext())\n",
    "    even_tail.setnext(None)\n",
    "\n",
    "    return odd_head.getnext()\n",
    "\n",
    "# Creating the input linked list\n",
    "head = Node(1)\n",
    "node2 = Node(2)\n",
    "node3 = Node(3)\n",
    "node4 = Node(4)\n",
    "node5 = Node(5)\n",
    "\n",
    "# Linking the nodes\n",
    "head.setnext(node2)\n",
    "node2.setnext(node3)\n",
    "node3.setnext(node4)\n",
    "node4.setnext(node5)\n",
    "\n",
    "# Print the original linked list\n",
    "print(\"Original linked list:\")\n",
    "traverse(head)\n",
    "\n",
    "# Rearrange the linked list\n",
    "head = rearrange_linked_list(head)\n",
    "\n",
    "# Print the rearranged linked list\n",
    "print(\"Rearranged linked list:\")\n",
    "traverse(head)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6dbd42bb",
   "metadata": {},
   "source": [
    "# Problem 13: Given a non-negative number represented as a linked list, add one to it.\n",
    "## Input: 1 -> 2 -> 3 (represents the number 123)\n",
    "\n",
    "## Output: 1 -> 2 -> 4 (represents the number 124)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "4f5fae01",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original linked list:\n",
      "1 -> 2 -> 3 -> None\n",
      "Modified linked list:\n",
      "0 -> 1 -> 2 -> 4 -> None\n"
     ]
    }
   ],
   "source": [
    "# Defining the class Node\n",
    "class Node:\n",
    "    def __init__(self, data=None, next=None):\n",
    "        self.data = data\n",
    "        self.next = next\n",
    "\n",
    "    # Method to set the data \n",
    "    def setdata(self, data):\n",
    "        self.data = data\n",
    "\n",
    "    # Method to get the data\n",
    "    def getdata(self):\n",
    "        return self.data\n",
    "\n",
    "    # Method to set the next\n",
    "    def setnext(self, next):\n",
    "        self.next = next\n",
    "\n",
    "    # Method to get the next\n",
    "    def getnext(self):\n",
    "        return self.next\n",
    "\n",
    "# Function to traverse through the linked list\n",
    "def traverse(head):\n",
    "    temp = head\n",
    "    while temp:\n",
    "        print(temp.getdata(), end=\" -> \")\n",
    "        temp = temp.getnext()\n",
    "    print(\"None\")\n",
    "\n",
    "def add_one(head):\n",
    "    # Initialize carry to 1\n",
    "    carry = 1\n",
    "    dummy = Node(0)\n",
    "    dummy.setnext(head)\n",
    "    current = head\n",
    "    last_non_nine = dummy\n",
    "    \n",
    "    # Traverse the linked list from right to left\n",
    "    while current:\n",
    "        if current.getdata() != 9:\n",
    "            last_non_nine = current\n",
    "        current = current.getnext()\n",
    "    \n",
    "    # Add one to the last non-nine node\n",
    "    last_non_nine.setdata(last_non_nine.getdata() + 1)\n",
    "    \n",
    "    # Update the nodes after the last non-nine node\n",
    "    current = last_non_nine.getnext()\n",
    "    while current:\n",
    "        current.setdata(0)\n",
    "        current = current.getnext()\n",
    "    \n",
    "    # If the dummy node's value is 1, return dummy.next, otherwise return dummy\n",
    "    if dummy.getdata() == 1:\n",
    "        return dummy.getnext()\n",
    "    else:\n",
    "        return dummy\n",
    "\n",
    "# Creating the input linked list\n",
    "head = Node(1)\n",
    "node2 = Node(2)\n",
    "node3 = Node(3)\n",
    "\n",
    "# Linking the nodes\n",
    "head.setnext(node2)\n",
    "node2.setnext(node3)\n",
    "\n",
    "# Print the original linked list\n",
    "print(\"Original linked list:\")\n",
    "traverse(head)\n",
    "\n",
    "# Add one to the linked list\n",
    "head = add_one(head)\n",
    "\n",
    "# Print the modified linked list\n",
    "print(\"Modified linked list:\")\n",
    "traverse(head)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "87dca414",
   "metadata": {},
   "source": [
    "# Problem 14: Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be inserted.\n",
    "## Input: nums = [1, 3, 5, 6], target = 5\n",
    "\n",
    "## Output: 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "dcd37fb0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input: [1, 3, 5, 6] Target: 5\n",
      "Output: 2\n"
     ]
    }
   ],
   "source": [
    "def search_insert_position(nums, target):\n",
    "    # Base case: If the array is empty, return 0\n",
    "    if not nums:\n",
    "        return 0\n",
    "    \n",
    "    left, right = 0, len(nums) - 1\n",
    "    \n",
    "    while left <= right:\n",
    "        mid = left + (right - left) // 2\n",
    "        \n",
    "        # If target is found, return the index\n",
    "        if nums[mid] == target:\n",
    "            return mid\n",
    "        \n",
    "        # If target is smaller than the value at mid, search in the left half\n",
    "        elif nums[mid] > target:\n",
    "            right = mid - 1\n",
    "            \n",
    "        # If target is larger than the value at mid, search in the right half\n",
    "        else:\n",
    "            left = mid + 1\n",
    "    \n",
    "    # If target is not found, left will be the index where it would be inserted\n",
    "    return left\n",
    "\n",
    "# Test the function\n",
    "nums = [1, 3, 5, 6]\n",
    "target = 5\n",
    "print(\"Input:\", nums, \"Target:\", target)\n",
    "print(\"Output:\", search_insert_position(nums, target))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "567adf87",
   "metadata": {},
   "source": [
    "# Problem 15: Find the minimum element in a rotated sorted array.\n",
    "## Input: [4, 5, 6, 7, 0, 1, 2]\n",
    "\n",
    "## Output: 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "42f4583b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input: [4, 5, 6, 7, 0, 1, 2]\n",
      "Output: 0\n"
     ]
    }
   ],
   "source": [
    "def find_min_in_rotated_array(nums):\n",
    "    left, right = 0, len(nums) - 1\n",
    "    \n",
    "    while left < right:\n",
    "        mid = left + (right - left) // 2\n",
    "        \n",
    "        # If the middle element is greater than the last element, search in the right half\n",
    "        if nums[mid] > nums[right]:\n",
    "            left = mid + 1\n",
    "        # If the middle element is smaller than or equal to the last element, search in the left half\n",
    "        else:\n",
    "            right = mid\n",
    "    \n",
    "    # At the end of the loop, left will point to the minimum element\n",
    "    return nums[left]\n",
    "\n",
    "# Test the function\n",
    "nums = [4, 5, 6, 7, 0, 1, 2]\n",
    "print(\"Input:\", nums)\n",
    "print(\"Output:\", find_min_in_rotated_array(nums))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6c447788",
   "metadata": {},
   "source": [
    "# Problem 16: Search for a target value in a rotated sorted array.\n",
    "## Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0\n",
    "\n",
    "## Output: 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "208cfac2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input: [4, 5, 6, 7, 0, 1, 2] Target: 0\n",
      "Output: 4\n"
     ]
    }
   ],
   "source": [
    "def search_rotated_sorted_array(nums, target):\n",
    "    left, right = 0, len(nums) - 1\n",
    "    \n",
    "    while left <= right:\n",
    "        mid = left + (right - left) // 2\n",
    "        \n",
    "        if nums[mid] == target:\n",
    "            return mid\n",
    "        \n",
    "        # Check if left half is sorted\n",
    "        if nums[left] <= nums[mid]:\n",
    "            # Check if target lies in the left half\n",
    "            if nums[left] <= target < nums[mid]:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        # Right half is sorted\n",
    "        else:\n",
    "            # Check if target lies in the right half\n",
    "            if nums[mid] < target <= nums[right]:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "    \n",
    "    return -1\n",
    "\n",
    "# Test the function\n",
    "nums = [4, 5, 6, 7, 0, 1, 2]\n",
    "target = 0\n",
    "print(\"Input:\", nums, \"Target:\", target)\n",
    "print(\"Output:\", search_rotated_sorted_array(nums, target))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ae67c8a5",
   "metadata": {},
   "source": [
    "# Problem 17: Find the peak element in an array. A peak element is greater than its neighbors.\n",
    "## Input: nums = [1, 2, 3, 1]\n",
    "\n",
    "## Output: 2 (index of peak element)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "1a6ac40f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input: [1, 2, 3, 1]\n",
      "Output: 2 (index of peak element)\n"
     ]
    }
   ],
   "source": [
    "def find_peak_element(nums):\n",
    "    left, right = 0, len(nums) - 1\n",
    "    \n",
    "    while left < right:\n",
    "        mid = left + (right - left) // 2\n",
    "        \n",
    "        # Check if mid is a peak element\n",
    "        if nums[mid] > nums[mid + 1]:\n",
    "            right = mid\n",
    "        else:\n",
    "            left = mid + 1\n",
    "            \n",
    "    return left\n",
    "\n",
    "# Test the function\n",
    "nums = [1, 2, 3, 1]\n",
    "print(\"Input:\", nums)\n",
    "print(\"Output:\", find_peak_element(nums),\"(index of peak element)\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2138ea92",
   "metadata": {},
   "source": [
    "# Problem 18: Given a m x n matrix where each row and column is sorted in ascending order, count the number of negative numbers.\n",
    "## Input: grid = [[4, 3, 2, -1], [3, 2, 1, -1], [1, 1, -1, -2], [-1, -1, -2, -3]]\n",
    "\n",
    "## Output: 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "4c8ec5a6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input:\n",
      "[4, 3, 2, -1]\n",
      "[3, 2, 1, -1]\n",
      "[1, 1, -1, -2]\n",
      "[-1, -1, -2, -3]\n",
      "Output: 8\n"
     ]
    }
   ],
   "source": [
    "def count_negatives(grid):\n",
    "    m, n = len(grid), len(grid[0])\n",
    "    count = 0\n",
    "    row, col = 0, n - 1  # Start from the top-right corner\n",
    "\n",
    "    while row < m and col >= 0:\n",
    "        if grid[row][col] < 0:\n",
    "            # All elements to the left of grid[row][col] will also be negative\n",
    "            count += (m - row)\n",
    "            col -= 1  # Move left\n",
    "        else:\n",
    "            row += 1  # Move down\n",
    "    \n",
    "    return count\n",
    "\n",
    "# Test the function\n",
    "grid = [\n",
    "    [4, 3, 2, -1],\n",
    "    [3, 2, 1, -1],\n",
    "    [1, 1, -1, -2],\n",
    "    [-1, -1, -2, -3]\n",
    "]\n",
    "print(\"Input:\")\n",
    "for row in grid:\n",
    "    print(row)\n",
    "print(\"Output:\", count_negatives(grid))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "912136d3",
   "metadata": {},
   "source": [
    "# Problem 19: Given a 2D matrix sorted in ascending order in each row, and the first integer of each row is greater than the last integer of the previous row, determine if a target value is present in the matrix.\n",
    "## Input: matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], target = 3\n",
    "\n",
    "## Output: True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "9c6303e4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input:\n",
      "[1, 3, 5, 7]\n",
      "[10, 11, 16, 20]\n",
      "[23, 30, 34, 60]\n",
      "Target: 3\n",
      "Output: True\n"
     ]
    }
   ],
   "source": [
    "def search_matrix(matrix, target):\n",
    "    if not matrix or not matrix[0]:\n",
    "        return False\n",
    "    \n",
    "    m, n = len(matrix), len(matrix[0])\n",
    "    left, right = 0, m * n - 1\n",
    "    \n",
    "    while left <= right:\n",
    "        mid = left + (right - left) // 2\n",
    "        mid_val = matrix[mid // n][mid % n]\n",
    "        \n",
    "        if mid_val == target:\n",
    "            return True\n",
    "        elif mid_val < target:\n",
    "            left = mid + 1\n",
    "        else:\n",
    "            right = mid - 1\n",
    "    \n",
    "    return False\n",
    "\n",
    "# Test the function\n",
    "matrix = [\n",
    "    [1, 3, 5, 7],\n",
    "    [10, 11, 16, 20],\n",
    "    [23, 30, 34, 60]\n",
    "]\n",
    "target = 3\n",
    "print(\"Input:\")\n",
    "for row in matrix:\n",
    "    print(row)\n",
    "print(\"Target:\", target)\n",
    "print(\"Output:\", search_matrix(matrix, target))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6b71e35f",
   "metadata": {},
   "source": [
    "# Problem 20: Find Median in Two Sorted Arrays\n",
    "\n",
    "# Problem: Given two sorted arrays, find the median of the combined sorted array\n",
    "## Input: nums1 = [1, 3], nums2 = [2]\n",
    "\n",
    "## Output: 2.0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "667bad30",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input:\n",
      "nums1 = [1, 3]\n",
      "nums2 = [2]\n",
      "Median: 2\n"
     ]
    }
   ],
   "source": [
    "def find_median_sorted_arrays(nums1, nums2):\n",
    "    merged = []\n",
    "    i, j = 0, 0\n",
    "    \n",
    "    while i < len(nums1) and j < len(nums2):\n",
    "        if nums1[i] < nums2[j]:\n",
    "            merged.append(nums1[i])\n",
    "            i += 1\n",
    "        else:\n",
    "            merged.append(nums2[j])\n",
    "            j += 1\n",
    "    \n",
    "    # Add remaining elements from nums1 (if any)\n",
    "    while i < len(nums1):\n",
    "        merged.append(nums1[i])\n",
    "        i += 1\n",
    "    \n",
    "    # Add remaining elements from nums2 (if any)\n",
    "    while j < len(nums2):\n",
    "        merged.append(nums2[j])\n",
    "        j += 1\n",
    "    \n",
    "    n = len(merged)\n",
    "    if n % 2 == 0:\n",
    "        return (merged[n // 2 - 1] + merged[n // 2]) / 2\n",
    "    else:\n",
    "        return merged[n // 2]\n",
    "\n",
    "# Test the function\n",
    "nums1 = [1, 3]\n",
    "nums2 = [2]\n",
    "print(\"Input:\")\n",
    "print(\"nums1 =\", nums1)\n",
    "print(\"nums2 =\", nums2)\n",
    "print(\"Median:\", find_median_sorted_arrays(nums1, nums2))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d383ada5",
   "metadata": {},
   "source": [
    "# Problem 21: Given a sorted character array and a target letter, find the smallest letter in the array that is greater than the target.\n",
    "## Input: letters = ['c', 'f', 'j'], target = a\n",
    "## Output: 'c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "72cdae3a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Input:\n",
      "letters = ['c', 'f', 'j']\n",
      "target = a\n",
      "Output: c\n"
     ]
    }
   ],
   "source": [
    "def next_greatest_letter(letters, target):\n",
    "    left, right = 0, len(letters) - 1\n",
    "    \n",
    "    while left <= right:\n",
    "        mid = left + (right - left) // 2\n",
    "        \n",
    "        # If mid is less than or equal to the target, search in the right half\n",
    "        if letters[mid] <= target:\n",
    "            left = mid + 1\n",
    "        # If mid is greater than the target, update the result and search in the left half\n",
    "        else:\n",
    "            result = letters[mid]\n",
    "            right = mid - 1\n",
    "            \n",
    "    # If all letters are less than or equal to the target, return the first letter\n",
    "    return letters[left % len(letters)]\n",
    "\n",
    "# Test the function\n",
    "letters = ['c', 'f', 'j']\n",
    "target = 'a'\n",
    "print(\"Input:\")\n",
    "print(\"letters =\", letters)\n",
    "print(\"target =\", target)\n",
    "print(\"Output:\", next_greatest_letter(letters, target))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5324b68f",
   "metadata": {},
   "source": [
    "# Problem 22: Given an array with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.\n",
    "\n",
    "Input: nums = [2, 0, 2, 1, 1, 0]\n",
    "\n",
    "Output: [0, 0, 1, 1, 2, 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "224b8141",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 0, 1, 1, 2, 2]\n"
     ]
    }
   ],
   "source": [
    "def sortColors(nums):\n",
    "    # Initialize pointers for the boundaries of each color\n",
    "    red, white, blue = 0, 0, len(nums) - 1\n",
    "    \n",
    "    # Iterate through the array\n",
    "    while white <= blue:\n",
    "        if nums[white] == 0:\n",
    "            # If the current element is 0, swap it with the element at the red pointer\n",
    "            nums[red], nums[white] = nums[white], nums[red]\n",
    "            # Move both red and white pointers to the right\n",
    "            red += 1\n",
    "            white += 1\n",
    "        elif nums[white] == 1:\n",
    "            # If the current element is 1, just move the white pointer to the right\n",
    "            white += 1\n",
    "        else:\n",
    "            # If the current element is 2, swap it with the element at the blue pointer\n",
    "            nums[white], nums[blue] = nums[blue], nums[white]\n",
    "            # Move the blue pointer to the left\n",
    "            blue -= 1\n",
    "\n",
    "\n",
    "            \n",
    "nums = [2, 0, 2, 1, 1, 0]\n",
    "sortColors(nums)\n",
    "print(nums) \n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eb258bb4",
   "metadata": {},
   "source": [
    "# Problem 23: Find the kth largest element in an unsorted array.\n",
    "Input: nums = [3, 2, 1, 5, 6, 4], k = 2\n",
    "\n",
    "Output: 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "9c796bce",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "# first we sort the array in descending order\n",
    "def bubblesort(arr):\n",
    "    for i in range(len(arr)-1, 0, -1):\n",
    "        for j in range(i):\n",
    "            if (arr[j] < arr[j+1]):\n",
    "                arr[j],arr[j+1] = arr[j+1],arr[j]\n",
    "    return arr\n",
    "\n",
    "def find_k_largest(arr,k):\n",
    "    bubblesort(arr)\n",
    "    return arr[k-1]\n",
    "\n",
    "print(find_k_largest([3, 2, 1, 5, 6, 4], k = 2))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "460132ce",
   "metadata": {},
   "source": [
    "# Problem 24: Given an unsorted array, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]...\n",
    "\n",
    "Input: nums = [3, 5, 2, 1, 6, 4]\n",
    "\n",
    "Output: [3, 5, 1, 6, 2, 4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "bc241cf8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 5, 1, 6, 2, 4]\n"
     ]
    }
   ],
   "source": [
    "def altSort(nums):\n",
    "\n",
    "    # Iterate through the array starting from the second element\n",
    "    for i in range(1, len(nums)):\n",
    "        if (i % 2 == 0 and nums[i] > nums[i - 1]) or (i % 2 != 0 and nums[i] < nums[i - 1]):\n",
    "            nums[i], nums[i - 1] = nums[i - 1], nums[i]\n",
    "\n",
    "# Test the function with the given input\n",
    "nums = [3, 5, 2, 1, 6, 4]\n",
    "altSort(nums)\n",
    "print(nums)  \n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "551a75cc",
   "metadata": {},
   "source": [
    "# Problem 25: Given an array of integers, calculate the sum of all its elements\n",
    "Input: [1, 2, 3, 4, 5]\n",
    "\n",
    "Output: 15"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "f38ca1f5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15\n"
     ]
    }
   ],
   "source": [
    "def sum_arr(arr):\n",
    "    sumele = 0\n",
    "    for _ in arr:\n",
    "        sumele += _\n",
    "    return sumele\n",
    "print(sum_arr([1,2,3,4,5]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "86d6abc8",
   "metadata": {},
   "source": [
    "# Problem 26: Find the maximum element in an array of integers.\n",
    "Input: [3, 7, 2, 9, 4, 1]\n",
    "\n",
    "Output: 9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "02dca99a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9\n"
     ]
    }
   ],
   "source": [
    "def find_max_ele(arr):\n",
    "    max_ele = arr[0]\n",
    "    for i in arr:\n",
    "        if i > max_ele:\n",
    "            max_ele = i\n",
    "    return max_ele\n",
    "print(find_max_ele([3,7,2,9,4,1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0ceae2b3",
   "metadata": {},
   "source": [
    "# Problem 27: Implement linear search to find the index of a target element in an array.\n",
    "\n",
    "Input: [5, 3, 8, 2, 7, 4], target = 8\n",
    "\n",
    "Output: 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "4870578b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "def find_index(arr,target):\n",
    "    for i in range(len(arr)):\n",
    "        if arr[i] == target:\n",
    "            return i \n",
    "    return -1 #when target is not in array\n",
    "print(find_index([5,3,8,2,7,4],8))\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7776674f",
   "metadata": {},
   "source": [
    "# Problem 28: Calculate the factorial of a given number.\n",
    "\n",
    "Input: 5\n",
    "\n",
    "Output: 120 (as 5! = 5 * 4 * 3 * 2 * 1 = 120)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "5e2eab1e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "120\n"
     ]
    }
   ],
   "source": [
    "def fact(num):\n",
    "    if num == 0 or n == 1:\n",
    "        return 1\n",
    "    else:\n",
    "        return num*fact(num-1)\n",
    "print(fact(5))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3da74e99",
   "metadata": {},
   "source": [
    "# Problem 29: Check if a given number is a prime number.\n",
    "\n",
    "Input: 7\n",
    "\n",
    "Output: True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "b259a390",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "def isprime(num):\n",
    "    if num < 2:\n",
    "        return False\n",
    "    if num == 2:\n",
    "        return True\n",
    "    if num % 2 == 0:\n",
    "        return False\n",
    "    for i in range(3, int(num**0.5) + 1, 2):\n",
    "        if num % i == 0:\n",
    "            return False\n",
    "    return True\n",
    "print(isprime(7))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "99249805",
   "metadata": {},
   "source": [
    "# Problem 30: Generate the Fibonacci series up to a given number n.\n",
    "Input: 8\n",
    "\n",
    "Output: [0, 1, 1, 2, 3, 5, 8, 13]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "598148e9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 1, 2, 3, 5, 8, 13]\n"
     ]
    }
   ],
   "source": [
    "def fibonacci(n):\n",
    "    fib_series = [0, 1] \n",
    "    for i in range(2, n):\n",
    "        fib_series.append(fib_series[-1] + fib_series[-2]) \n",
    "    return fib_series\n",
    "\n",
    "# Test the function with the given input\n",
    "print(fibonacci(8))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6da6c143",
   "metadata": {},
   "source": [
    "# Problem 31: Calculate the power of a number using recursion\n",
    "\n",
    "Input: base = 3, exponent = 4\n",
    "\n",
    "Output: 81 (as 3^4 = 3 * 3 * 3 * 3 = 81)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "4939ec3d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "81\n"
     ]
    }
   ],
   "source": [
    "def power(base,exponent):\n",
    "    if exponent == 0:\n",
    "        return 1\n",
    "    elif exponent == 1:\n",
    "        return base\n",
    "    else:\n",
    "        return base * power(base,exponent-1)\n",
    "    \n",
    "print(power(3,4))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e46b7274",
   "metadata": {},
   "source": [
    "# Problem 32: Reverse a given string.\n",
    "\n",
    "Input: \"hello\"\n",
    "\n",
    "Output: \"olleh\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "9f315065",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Reversed string: olleh\n"
     ]
    }
   ],
   "source": [
    "def rev_str(string):\n",
    "    rev = \"\"\n",
    "    for char in string:\n",
    "        rev = char + rev\n",
    "    return rev\n",
    "\n",
    "print(\"Reversed string:\",rev_str(\"hello\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a2b20edf",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.5"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}