FSDS_DSA_ASSGINMENT_SOLS.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "source": [
        "Problem 1: Reverse a singly linked list.\n"
      ],
      "metadata": {
        "id": "CABoiqOYibA2"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {
        "id": "YTrSf5LAiJDZ"
      },
      "outputs": [],
      "source": [
        "class ListNode:\n",
        "    def __init__(self, val=0, next=None):\n",
        "        self.val = val\n",
        "        self.next = next\n",
        "\n",
        "def reverse_linked_list(head):\n",
        "    prev = None\n",
        "    current = head\n",
        "\n",
        "    while current:\n",
        "        next_node = current.next\n",
        "        current.next = prev\n",
        "        prev = current\n",
        "        current = next_node\n",
        "\n",
        "    return prev\n"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Problem 2: Merge two sorted linked lists into one sorted linked list.\n"
      ],
      "metadata": {
        "id": "2TQENOnYic9t"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def merge_two_lists(l1, l2):\n",
        "    dummy = ListNode()\n",
        "    current = dummy\n",
        "\n",
        "    while l1 and l2:\n",
        "        if l1.val < l2.val:\n",
        "            current.next = l1\n",
        "            l1 = l1.next\n",
        "        else:\n",
        "            current.next = l2\n",
        "            l2 = l2.next\n",
        "\n",
        "        current = current.next\n",
        "\n",
        "    current.next = l1 or l2\n",
        "\n",
        "    return dummy.next\n"
      ],
      "metadata": {
        "id": "FQn5Na_uiecs"
      },
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Problem 3: Remove the nth node from the end of a linked list.\n"
      ],
      "metadata": {
        "id": "pVOHbvonilNb"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def remove_nth_from_end(head, n):\n",
        "    dummy = ListNode(0)\n",
        "    dummy.next = head\n",
        "    slow = fast = dummy\n",
        "\n",
        "    for _ in range(n + 1):\n",
        "        fast = fast.next\n",
        "\n",
        "    while fast:\n",
        "        slow = slow.next\n",
        "        fast = fast.next\n",
        "\n",
        "    slow.next = slow.next.next\n",
        "\n",
        "    return dummy.next\n"
      ],
      "metadata": {
        "id": "hyO7SK-BilsT"
      },
      "execution_count": 6,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Problem 4: Find the intersection point of two linked lists.\n"
      ],
      "metadata": {
        "id": "QBemRnoOioOc"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def get_intersection_node(headA, headB):\n",
        "    if not headA or not headB:\n",
        "        return None\n",
        "\n",
        "    a, b = headA, headB\n",
        "\n",
        "    while a != b:\n",
        "        a = a.next if a else headB\n",
        "        b = b.next if b else headA\n",
        "\n",
        "    return a\n"
      ],
      "metadata": {
        "id": "yKXgdnddiofW"
      },
      "execution_count": 7,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Problem 5: Remove duplicates from a sorted linked list.\n"
      ],
      "metadata": {
        "id": "RikHN5WOitHv"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def delete_duplicates(head):\n",
        "    current = head\n",
        "\n",
        "    while current and current.next:\n",
        "        if current.val == current.next.val:\n",
        "            current.next = current.next.next\n",
        "        else:\n",
        "            current = current.next\n",
        "\n",
        "    return head\n"
      ],
      "metadata": {
        "id": "CnlgRzx6itww"
      },
      "execution_count": 8,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Problem 6: Add two numbers represented by linked lists (where each node contains a single digit)."
      ],
      "metadata": {
        "id": "e3HWjVmqiw9x"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def add_two_numbers(l1, l2):\n",
        "    dummy = ListNode()\n",
        "    current = dummy\n",
        "    carry = 0\n",
        "\n",
        "    while l1 or l2 or carry:\n",
        "        sum_val = (l1.val if l1 else 0) + (l2.val if l2 else 0) + carry\n",
        "        carry, digit = divmod(sum_val, 10)\n",
        "\n",
        "        current.next = ListNode(digit)\n",
        "        current = current.next\n",
        "\n",
        "        l1 = l1.next if l1 else None\n",
        "        l2 = l2.next if l2 else None\n",
        "\n",
        "    return dummy.next\n"
      ],
      "metadata": {
        "id": "yqeDww4ziwsH"
      },
      "execution_count": 9,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Problem 7: Swap nodes in pairs in a linked list.\n"
      ],
      "metadata": {
        "id": "sWGuWEBpiz5_"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def swap_pairs(head):\n",
        "    dummy = ListNode()\n",
        "    dummy.next = head\n",
        "    current = dummy\n",
        "\n",
        "    while current.next and current.next.next:\n",
        "        first = current.next\n",
        "        second = current.next.next\n",
        "\n",
        "        first.next = second.next\n",
        "        current.next = second\n",
        "        current.next.next = first\n",
        "\n",
        "        current = current.next.next\n",
        "\n",
        "    return dummy.next\n"
      ],
      "metadata": {
        "id": "Wr-hWKgti1He"
      },
      "execution_count": 10,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Problem 8: Reverse nodes in a linked list in groups of k.\n"
      ],
      "metadata": {
        "id": "QyaFQdIti2uH"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def reverse_k_group(head, k):\n",
        "    def reverse_group(start, end):\n",
        "        prev, current = end, start\n",
        "\n",
        "        while current != end:\n",
        "            next_node = current.next\n",
        "            current.next = prev\n",
        "            prev = current\n",
        "            current = next_node\n",
        "\n",
        "        return prev\n",
        "\n",
        "    dummy = ListNode()\n",
        "    dummy.next = head\n",
        "    current = dummy\n",
        "\n",
        "    while True:\n",
        "        start = current.next\n",
        "        end = current\n",
        "\n",
        "        for _ in range(k):\n",
        "            end = end.next\n",
        "            if not end:\n",
        "                return dummy.next\n",
        "\n",
        "        current.next = reverse_group(start, end)\n",
        "        start.next = end\n",
        "        current = start\n"
      ],
      "metadata": {
        "id": "rgZsDIGyi2Rw"
      },
      "execution_count": 11,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Problem 9: Determine if a linked list is a palindrome.\n"
      ],
      "metadata": {
        "id": "A9Xy3nEzi_kV"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def is_palindrome(head):\n",
        "    def reverse_linked_list(node):\n",
        "        prev = None\n",
        "        current = node\n",
        "\n",
        "        while current:\n",
        "            next_node = current.next\n",
        "            current.next = prev\n",
        "            prev = current\n",
        "            current = next_node\n",
        "\n",
        "        return prev\n",
        "\n",
        "    slow = fast = head\n",
        "\n",
        "    while fast and fast.next:\n",
        "        slow = slow.next\n",
        "        fast = fast.next.next\n",
        "\n",
        "    reversed_half = reverse_linked_list(slow)\n",
        "    current = head\n",
        "\n",
        "    while reversed_half:\n",
        "        if current.val != reversed_half.val:\n",
        "            return False\n",
        "\n",
        "        current = current.next\n",
        "        reversed_half = reversed_half.next\n",
        "\n",
        "    return True\n"
      ],
      "metadata": {
        "id": "CFz0fd9Ei_6A"
      },
      "execution_count": 12,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Problem 10: Rotate a linked list to the right by k places.\n"
      ],
      "metadata": {
        "id": "0fwwF6-bjBZj"
      }
    },
    {
      "cell_type": "code",
      "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.next:\n",
        "        tail = tail.next\n",
        "        length += 1\n",
        "\n",
        "    # Calculate the effective rotation amount\n",
        "    k = k % length\n",
        "\n",
        "    # If k is 0, no rotation is needed\n",
        "    if k == 0:\n",
        "        return head\n",
        "\n",
        "    # Find the new head and break the loop at the rotation point\n",
        "    new_head_position = length - k\n",
        "    new_tail = head\n",
        "    for _ in range(new_head_position - 1):\n",
        "        new_tail = new_tail.next\n",
        "\n",
        "    new_head = new_tail.next\n",
        "    new_tail.next = None\n",
        "    tail.next = head\n",
        "\n",
        "    return new_head\n"
      ],
      "metadata": {
        "id": "h66pageFjDHD"
      },
      "execution_count": 13,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Problem 11: Flatten a multilevel doubly linked list.\n"
      ],
      "metadata": {
        "id": "yOerpZjvjMZr"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class Node:\n",
        "    def __init__(self, val, 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",
        "    dummy = Node(0, None, head, None)\n",
        "    current = dummy\n",
        "\n",
        "    stack = [head]\n",
        "\n",
        "    while stack:\n",
        "        node = stack.pop()\n",
        "\n",
        "        if node.next:\n",
        "            stack.append(node.next)\n",
        "\n",
        "        if node.child:\n",
        "            stack.append(node.child)\n",
        "            node.child = None\n",
        "\n",
        "        current.next = node\n",
        "        node.prev = current\n",
        "        current = node\n",
        "\n",
        "    dummy.next.prev = None\n",
        "\n",
        "    return dummy.next\n"
      ],
      "metadata": {
        "id": "J8apycsijMxf"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Problem 12: Rearrange a linked list such that all even positioned nodes are placed at the end."
      ],
      "metadata": {
        "id": "CqcmZcSyjN_p"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class ListNode:\n",
        "    def __init__(self, val=0, next=None):\n",
        "        self.val = val\n",
        "        self.next = next\n",
        "\n",
        "def rearrange_linked_list(head):\n",
        "    if not head or not head.next or not head.next.next:\n",
        "        return head\n",
        "\n",
        "    odd_head = head\n",
        "    even_head = head.next\n",
        "    odd_current = odd_head\n",
        "    even_current = even_head\n",
        "\n",
        "    while even_current and even_current.next:\n",
        "        odd_current.next = even_current.next\n",
        "        odd_current = odd_current.next\n",
        "\n",
        "        even_current.next = odd_current.next\n",
        "        even_current = even_current.next\n",
        "\n",
        "    odd_current.next = even_head\n",
        "\n",
        "    return odd_head\n"
      ],
      "metadata": {
        "id": "aeeXU7KrjZfh"
      },
      "execution_count": 14,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Problem 13: Given a non-negative number represented as a linked list, add one to it.\n"
      ],
      "metadata": {
        "id": "bpQLqNWsjchz"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class ListNode:\n",
        "    def __init__(self, val=0, next=None):\n",
        "        self.val = val\n",
        "        self.next = next\n",
        "\n",
        "def add_one_to_linked_list(head):\n",
        "    dummy = ListNode(0)\n",
        "    dummy.next = head\n",
        "    not_nine = dummy\n",
        "\n",
        "    current = head\n",
        "    while current:\n",
        "        if current.val != 9:\n",
        "            not_nine = current\n",
        "        current = current.next\n",
        "\n",
        "    not_nine.val += 1\n",
        "    not_nine = not_nine.next\n",
        "\n",
        "    while not_nine:\n",
        "        not_nine.val = 0\n",
        "        not_nine = not_nine.next\n",
        "\n",
        "    return dummy.next if dummy.val == 1 else dummy.next.next\n"
      ],
      "metadata": {
        "id": "zLLTSxMajbTL"
      },
      "execution_count": 15,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "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"
      ],
      "metadata": {
        "id": "OUH7h8uyjfdE"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def search_insert(nums, target):\n",
        "    left, right = 0, len(nums)\n",
        "\n",
        "    while left < right:\n",
        "        mid = (left + right) // 2\n",
        "\n",
        "        if nums[mid] == target:\n",
        "            return mid\n",
        "        elif nums[mid] < target:\n",
        "            left = mid + 1\n",
        "        else:\n",
        "            right = mid\n",
        "\n",
        "    return left\n"
      ],
      "metadata": {
        "id": "CNA5HlCCjhHX"
      },
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Problem 15: Find the minimum element in a rotated sorted array.\n"
      ],
      "metadata": {
        "id": "r2HhDneSjivo"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def find_min(nums):\n",
        "    left, right = 0, len(nums) - 1\n",
        "\n",
        "    while left < right:\n",
        "        mid = (left + right) // 2\n",
        "\n",
        "        if nums[mid] > nums[right]:\n",
        "            left = mid + 1\n",
        "        else:\n",
        "            right = mid\n",
        "\n",
        "    return nums[left]\n"
      ],
      "metadata": {
        "id": "qs3DoP5ajjQx"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Problem 16: Search for a target value in a rotated sorted array.\n"
      ],
      "metadata": {
        "id": "Qq6dKQtEjlst"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def search_rotated(nums, target):\n",
        "    left, right = 0, len(nums) - 1\n",
        "\n",
        "    while left <= right:\n",
        "        mid = (left + right) // 2\n",
        "\n",
        "        if nums[mid] == target:\n",
        "            return mid\n",
        "\n",
        "        if nums[left] <= nums[mid]:\n",
        "            if nums[left] <= target <= nums[mid]:\n",
        "                right = mid - 1\n",
        "            else:\n",
        "                left = mid + 1\n",
        "        else:\n",
        "            if nums[mid] <= target <= nums[right]:\n",
        "                left = mid + 1\n",
        "            else:\n",
        "                right = mid - 1\n",
        "\n",
        "    return -1\n"
      ],
      "metadata": {
        "id": "TbENacVRjl-c"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Problem 17: Find the peak element in an array. A peak element is greater than its neighbors.\n"
      ],
      "metadata": {
        "id": "7ybLsjWajntC"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def find_peak_element(nums):\n",
        "    left, right = 0, len(nums) - 1\n",
        "\n",
        "    while left < right:\n",
        "        mid = (left + right) // 2\n",
        "\n",
        "        if nums[mid] > nums[mid + 1]:\n",
        "            right = mid\n",
        "        else:\n",
        "            left = mid + 1\n",
        "\n",
        "    return left\n"
      ],
      "metadata": {
        "id": "E1fVgxpUjoD8"
      },
      "execution_count": 17,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "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"
      ],
      "metadata": {
        "id": "5sKXX_HMjqHf"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def count_negatives(grid):\n",
        "    count = 0\n",
        "    row, col = len(grid), len(grid[0])\n",
        "    r, c = 0, col - 1\n",
        "\n",
        "    while r < row and c >= 0:\n",
        "        if grid[r][c] < 0:\n",
        "            count += row - r\n",
        "            c -= 1\n",
        "        else:\n",
        "            r += 1\n",
        "\n",
        "    return count\n"
      ],
      "metadata": {
        "id": "d6G97hoZjqXD"
      },
      "execution_count": 18,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "\n",
        "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."
      ],
      "metadata": {
        "id": "3IpAb-Oyj07t"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def search_matrix(matrix, target):\n",
        "    if not matrix or not matrix[0]:\n",
        "        return False\n",
        "\n",
        "    rows, cols = len(matrix), len(matrix[0])\n",
        "    row, col = 0, cols - 1\n",
        "\n",
        "    while row < rows and col >= 0:\n",
        "        if matrix[row][col] == target:\n",
        "            return True\n",
        "        elif matrix[row][col] < target:\n",
        "            row += 1\n",
        "        else:\n",
        "            col -= 1\n",
        "\n",
        "    return False\n"
      ],
      "metadata": {
        "id": "FkoFZyEcj1RR"
      },
      "execution_count": 19,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Problem 20: Find Median in Two Sorted Arrays\n"
      ],
      "metadata": {
        "id": "PMmWqs8Ij5g6"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def findMedianSortedArrays(nums1, nums2):\n",
        "    nums = sorted(nums1 + nums2)\n",
        "    n = len(nums)\n",
        "\n",
        "    if n % 2 == 0:\n",
        "        mid1 = nums[n // 2]\n",
        "        mid2 = nums[n // 2 - 1]\n",
        "        return (mid1 + mid2) / 2\n",
        "    else:\n",
        "        return nums[n // 2]\n"
      ],
      "metadata": {
        "id": "m_zQHnaJj51O"
      },
      "execution_count": 20,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "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"
      ],
      "metadata": {
        "id": "_GHFHJo7j9yZ"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def nextGreatestLetter(letters, target):\n",
        "    for letter in letters:\n",
        "        if letter > target:\n",
        "            return letter\n",
        "    return letters[0]\n"
      ],
      "metadata": {
        "id": "III2MgiEj-4J"
      },
      "execution_count": 21,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "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"
      ],
      "metadata": {
        "id": "CudfHyW-kAiD"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def sortColors(nums):\n",
        "    low, mid, high = 0, 0, len(nums) - 1\n",
        "\n",
        "    while mid <= high:\n",
        "        if nums[mid] == 0:\n",
        "            nums[low], nums[mid] = nums[mid], nums[low]\n",
        "            low += 1\n",
        "            mid += 1\n",
        "        elif nums[mid] == 1:\n",
        "            mid += 1\n",
        "        else:\n",
        "            nums[mid], nums[high] = nums[high], nums[mid]\n",
        "            high -= 1\n",
        "\n",
        "# Example usage:\n",
        "# nums = [2, 0, 2, 1, 1, 0]\n",
        "# sortColors(nums)\n",
        "# print(nums)  # Output: [0, 0, 1, 1, 2, 2]\n"
      ],
      "metadata": {
        "id": "5C9tEZGDkA-8"
      },
      "execution_count": 22,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Problem 23: Find the kth largest element in an unsorted array.\n"
      ],
      "metadata": {
        "id": "s-YKF42akDOt"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def findKthLargest(nums, k):\n",
        "    nums.sort(reverse=True)\n",
        "    return nums[k - 1]\n"
      ],
      "metadata": {
        "id": "FItFhf6lkDku"
      },
      "execution_count": 23,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Problem 24: Given an unsorted array, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]...\n"
      ],
      "metadata": {
        "id": "8BqD9XlhkFDR"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def wiggleSort(nums):\n",
        "    nums.sort()\n",
        "    n = len(nums)\n",
        "    mid = (n - 1) // 2\n",
        "    nums[::2], nums[1::2] = nums[mid::-1], nums[:mid:-1]\n"
      ],
      "metadata": {
        "id": "iBCwVFrLkGb1"
      },
      "execution_count": 24,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Problem 25: Given an array of integers, calculate the sum of all its elements.\n",
        "\n"
      ],
      "metadata": {
        "id": "hsaSu1lbkJE4"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def array_sum(nums):\n",
        "    return sum(nums)\n"
      ],
      "metadata": {
        "id": "2pJigP8GkMUR"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Problem 26: Find the maximum element in an array of integers.\n"
      ],
      "metadata": {
        "id": "V2OmwvEZk24r"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def find_max_element(nums):\n",
        "    if not nums:\n",
        "        return None\n",
        "\n",
        "    max_element = nums[0]\n",
        "\n",
        "    for num in nums:\n",
        "        if num > max_element:\n",
        "            max_element = num\n",
        "\n",
        "    return max_element\n",
        "\n",
        "# Example usage:\n",
        "# nums = [3, 7, 2, 9, 4, 1]\n",
        "# max_element = find_max_element(nums)\n",
        "# print(max_element)  # Output: 9\n"
      ],
      "metadata": {
        "id": "xe37W18ok3Sr"
      },
      "execution_count": 25,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Problem 27 (Alternate Solution): Implement linear search to find the index of a target element in an array."
      ],
      "metadata": {
        "id": "hCFEQacUk9Od"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def linear_search(nums, target):\n",
        "    for i in range(len(nums)):\n",
        "        if nums[i] == target:\n",
        "            return i\n",
        "    return -1\n",
        "\n",
        "# Example usage:\n",
        "# nums = [5, 3, 8, 2, 7, 4]\n",
        "# target = 8\n",
        "# index = linear_search(nums, target)\n",
        "# print(index)  # Output: 2\n"
      ],
      "metadata": {
        "id": "JiC8REWFk-JM"
      },
      "execution_count": 26,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Problem 28: Calculate the factorial of a given number.\n"
      ],
      "metadata": {
        "id": "CMZoZLG8k_IO"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def factorial(n):\n",
        "    if n == 0 or n == 1:\n",
        "        return 1\n",
        "    else:\n",
        "        return n * factorial(n-1)\n",
        "\n",
        "# Example usage:\n",
        "# n = 5\n",
        "# result = factorial(n)\n",
        "# print(result)  # Output: 120\n"
      ],
      "metadata": {
        "id": "Lq_7_AS9lAci"
      },
      "execution_count": 27,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Problem 29: Check if a given number is a prime number.\n",
        "\n"
      ],
      "metadata": {
        "id": "perxLbOflCNx"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def is_prime(number):\n",
        "    if number < 2:\n",
        "        return False\n",
        "    for i in range(2, int(number**0.5) + 1):\n",
        "        if number % i == 0:\n",
        "            return False\n",
        "    return True\n",
        "\n",
        "# Example usage:\n",
        "# number = 7\n",
        "# result = is_prime(number)\n",
        "# print(result)  # Output: True\n"
      ],
      "metadata": {
        "id": "DVztKt_XlD7k"
      },
      "execution_count": 28,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Problem 30: Generate the Fibonacci series up to a given number n.\n"
      ],
      "metadata": {
        "id": "BB56W3g-lGkH"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def fibonacci_series(n):\n",
        "    fib_series = [0, 1]\n",
        "    while fib_series[-1] + fib_series[-2] <= n:\n",
        "        fib_series.append(fib_series[-1] + fib_series[-2])\n",
        "    return fib_series\n",
        "\n",
        "# Example usage:\n",
        "# n = 13\n",
        "# series = fibonacci_series(n)\n",
        "# print(series)  # Output: [0, 1, 1, 2, 3, 5, 8, 13]\n"
      ],
      "metadata": {
        "id": "SIBC9WAplHuZ"
      },
      "execution_count": 29,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Problem 31 (Alternate Solution): Calculate the power of a number using recursion."
      ],
      "metadata": {
        "id": "pEkphLTUlLTL"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def power(base, exponent):\n",
        "    if exponent == 0:\n",
        "        return 1\n",
        "    else:\n",
        "        return base * power(base, exponent - 1)\n",
        "\n",
        "# Example usage:\n",
        "# base = 3\n",
        "# exponent = 4\n",
        "# result = power(base, exponent)\n",
        "# print(result)  # Output: 81\n"
      ],
      "metadata": {
        "id": "n-izALzzlMaf"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Problem 32: Reverse a given string.\n"
      ],
      "metadata": {
        "id": "-cSMaVkxlN8j"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def reverse_string(s):\n",
        "    return s[::-1]\n",
        "\n",
        "# Example usage:\n",
        "# s = \"hello\"\n",
        "# reversed_str = reverse_string(s)\n",
        "# print(reversed_str)  # Output: \"olleh\"\n"
      ],
      "metadata": {
        "id": "ArtETRcNlOoG"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}