DAA_LAB1_PART3.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "rkTQfsa5PuGX",
        "outputId": "62a78430-1101-4b9b-cd5b-a2f6a89b26ee"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Enter the elements of the array: 2 4 5 9 6 7\n",
            "Enter the target sum: 5\n",
            "No pairs found with sum 5\n"
          ]
        }
      ],
      "source": [
        "def pairSum(arr, targ):\n",
        "    pair = []\n",
        "    visited = set()\n",
        "    for num in arr:\n",
        "        comp = targ - num\n",
        "        if comp in visited:\n",
        "            pair.append((comp, num))\n",
        "        visited.add(num)\n",
        "    return pair\n",
        "\n",
        "arr_inp = input(\"Enter the elements of the array: \")\n",
        "arr = list(map(int, arr_inp.split()))\n",
        "target = int(input(\"Enter the target sum: \"))\n",
        "\n",
        "pairs = pairSum(arr, target)\n",
        "if pairs:\n",
        "    print(\"Pairs with sum\", target, \":\")\n",
        "    print(pairs)\n",
        "else:\n",
        "    print(\"No pairs found with sum\", target)\n"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def max_product_pair(arr):\n",
        "    # Intializing max(for pos no) and min value(for neg no)\n",
        "    max1, max2 = float('-inf'), float('-inf')\n",
        "    min1, min2 = float('inf'), float('inf')\n",
        "    max_pair = None\n",
        "    # max product\n",
        "    for num in arr:\n",
        "        if num > max1:\n",
        "            max2 = max1\n",
        "            max1 = num\n",
        "        elif num > max2:\n",
        "            max2 = num\n",
        "\n",
        "        if num < min1:\n",
        "            min2 = min1\n",
        "            min1 = num\n",
        "        elif num < min2:\n",
        "            min2 = num\n",
        "\n",
        "    max_product = max(max1 * max2, min1 * min2)\n",
        "\n",
        "    # product pair\n",
        "    if max1 * max2 > min1 * min2:\n",
        "        max_pair = (max1, max2)\n",
        "    else:\n",
        "        max_pair = (min1, min2)\n",
        "\n",
        "    return max_product, max_pair\n",
        "\n",
        "arr_inp = input(\"Enter the elements of the array: \")\n",
        "arr = list(map(int, arr_inp.split()))\n",
        "max_product, max_pair = max_product_pair(arr)\n",
        "print(\"Max Product:\", max_product)\n",
        "print(\"Number pair :\", max_pair)\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lb2yTMOxRW3a",
        "outputId": "2abbdaaa-3883-4f11-9634-1a1d235de3d1"
      },
      "execution_count": 8,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Enter the elements of the array: 2 5 9 -8 -7\n",
            "Max Product: 56\n",
            "Number pair : (-8, -7)\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def sort_swapped_array(arr):\n",
        "    a1, a2 = None, None\n",
        "    for i in range(len(arr) - 1):\n",
        "        if arr[i] > arr[i + 1]:\n",
        "            if a1 is None:\n",
        "                a1 = i\n",
        "            else:\n",
        "                a2 = i + 1\n",
        "    y=arr[a1]\n",
        "    arr[a1]=arr[a2]\n",
        "    arr[a2]=y\n",
        "    #arr[first], arr[second] = arr[second], arr[first]\n",
        "    return arr\n",
        "\n",
        "arr_inp = input(\"Enter the elements of the array: \")\n",
        "arr = list(map(int, arr_inp.split()))\n",
        "print(sort_swapped_array(arr))\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "seygCdrmTTul",
        "outputId": "6c03267f-bd41-439b-937e-2555a1429e09"
      },
      "execution_count": 11,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Enter the elements of the array: 2 7 4 6 3 9\n",
            "[2, 3, 4, 6, 7, 9]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def segregate(arr):\n",
        "    left = 0\n",
        "    right= len(arr)-1\n",
        "    while left < right:\n",
        "        #move towards right after finding 0\n",
        "        while arr[left] == 0 and left < right:\n",
        "            left += 1\n",
        "        #move towards left after finding 1\n",
        "        while arr[right] == 1 and left < right:\n",
        "            right -= 1\n",
        "        if left < right:\n",
        "            y=arr[left]\n",
        "            arr[left]=arr[right]\n",
        "            arr[right]=y\n",
        "            left += 1\n",
        "            right -= 1\n",
        "    return arr\n",
        "\n",
        "# Example usage\n",
        "arr = [0, 1, 0, 1, 1, 0, 0, 1]\n",
        "print(segregate(arr))\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "2VSAyswlVIDo",
        "outputId": "904aa7de-802b-497f-b08c-732f195c9de4"
      },
      "execution_count": 12,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[0, 0, 0, 0, 1, 1, 1, 1]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "\n",
        "def merge(left, right, inv_pairs):\n",
        "    merged = []\n",
        "    inv_count = 0\n",
        "    i, j = 0, 0\n",
        "\n",
        "    while i < len(left) and j < len(right):\n",
        "        if left[i] <= right[j]:\n",
        "            merged.append(left[i])\n",
        "            i += 1\n",
        "        else:\n",
        "            merged.append(right[j])\n",
        "            j += 1\n",
        "            inv_count += len(left) - i\n",
        "            # When an inversion is found, add pair to inversion_pairs list\n",
        "            for x in range(i, len(left)):\n",
        "                inv_pairs.append((left[x], right[j-1]))\n",
        "\n",
        "    merged.extend(left[i:])\n",
        "    merged.extend(right[j:])\n",
        "\n",
        "    return merged, inv_count\n",
        "\n",
        "def merge_sort(arr, inv_pairs):\n",
        "    if len(arr) <= 1:\n",
        "        return arr, 0\n",
        "\n",
        "    mid = len(arr) // 2\n",
        "    left, left_count = merge_sort(arr[:mid], inv_pairs)\n",
        "    right, right_count = merge_sort(arr[mid:], inv_pairs)\n",
        "    merged, inv_count = merge(left, right, inv_pairs)\n",
        "\n",
        "    return merged, left_count + right_count + inv_count\n",
        "\n",
        "def inversion_count(arr):\n",
        "    inv_pairs = []\n",
        "    sorted_arr, count = merge_sort(arr, inv_pairs)\n",
        "    return count, inv_pairs\n",
        "\n",
        "# Input array\n",
        "A = [10, 1, 2, 13, 9, 5]\n",
        "\n",
        "# Calculate inversion count and pairs\n",
        "inversion_count, inversion_pairs = inversion_count(A)\n",
        "\n",
        "# Print inversion count\n",
        "print(\"Total count of inversions:\", inversion_count)\n",
        "\n",
        "# Print pairs of inversions\n",
        "print(\"Pairs of inversions:\\n\", inversion_pairs)\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "nCd8oczZgjaq",
        "outputId": "bd4b2186-a7a7-46b5-a66d-d3b0084468da"
      },
      "execution_count": 64,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Total count of inversions: 7\n",
            "Pairs of inversions:\n",
            " [(10, 1), (10, 2), (9, 5), (13, 5), (13, 9), (10, 5), (10, 9)]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def has_sum_n2(arr, K):\n",
        "    pairs = []\n",
        "    for i in range(len(arr)):\n",
        "        for j in range(i + 1, len(arr)):\n",
        "            if arr[i] + arr[j] == K:\n",
        "                pairs.append((arr[i], arr[j]))\n",
        "    return pairs\n",
        "\n",
        "arr_inp = input(\"Enter the elements of the array: \")\n",
        "arr = list(map(int, arr_inp.split()))\n",
        "k = int(input(\"Enter target sum: \"))\n",
        "\n",
        "targ_sum = has_sum_n2(arr, k)\n",
        "if targ_sum:\n",
        "    print(\"Pairs with sum\", k, \":\", targ_sum)\n",
        "else:\n",
        "    print(\"No pairs found with sum\", k)\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Gwr9a1ZNiP2H",
        "outputId": "9957c31a-458d-4d25-9577-0bca386d648f"
      },
      "execution_count": 69,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Enter the elements of the array: 2 4 6 8\n",
            "Enter target sum: 3\n",
            "No pairs found with sum 3\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def has_sum_nlogn(arr, K):\n",
        "    arr.sort()\n",
        "    pairs = []\n",
        "    left, right = 0, len(arr) - 1\n",
        "    while left < right:\n",
        "        curr_sum = arr[left] + arr[right]\n",
        "        if curr_sum == K:\n",
        "            pairs.append((arr[left], arr[right]))\n",
        "            left += 1  # Move left pointer forward\n",
        "            right -= 1  # Move right pointer backward\n",
        "        elif curr_sum < K:\n",
        "            left += 1\n",
        "        else:\n",
        "            right -= 1\n",
        "    return pairs\n",
        "\n",
        "arr_inp = input(\"Enter the elements of the array: \")\n",
        "arr = list(map(int, arr_inp.split()))\n",
        "k = int(input(\"Enter target sum: \"))\n",
        "targ_sum = has_sum_nlogn(arr, k)\n",
        "if targ_sum:\n",
        "    print(\"Pairs with sum\", k, \":\", targ_sum)\n",
        "else:\n",
        "    print(\"No pairs found with sum\", k)\n"
      ],
      "metadata": {
        "id": "TK1WoMHRkAiw",
        "outputId": "6186484f-5511-40aa-a6dd-6dc4c9b3c07b",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "execution_count": 67,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Pairs with sum 10 : [(4, 6)]\n"
          ]
        }
      ]
    }
  ]
}