26th_Nov_Sorting.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "580d9a6a-5c7c-4906-ac44-3566d7190aaa",
   "metadata": {},
   "source": [
    "                                                               Sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "934a1751-f769-4661-9347-953f7e615933",
   "metadata": {},
   "source": [
    "Problem 1.Given an array of n numbers, give an algorithm which gives the element appearing maximum\n",
    "number of times?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "0a128387-b6ae-46c2-9870-c9d7e340db14",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "def find_max_frequency_element(arr):\n",
    "    if not arr:\n",
    "        return None  # Handle empty array\n",
    "    frequency = {}\n",
    "    for num in arr:\n",
    "        frequency[num] = frequency.get(num, 0) + 1\n",
    "    return max(frequency, key=frequency.get)\n",
    "\n",
    "# Example usage:\n",
    "arr = [1, 2, 3, 2, 4, 2, 1, 3, 1, 1]\n",
    "print(find_max_frequency_element(arr))  # Output: 1\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d14afcb4-3be0-408f-a615-ce9901597e5e",
   "metadata": {},
   "source": [
    "Problem 2.We are given a list of n-1 integers and these integers are in the range of 1 to n . There are no\n",
    "duplicates in the list. One of the integers is missing in the list. Give an algorithm to find that element Ex:\n",
    "[1,2,4,6,3,7,8] 5 is the missing num."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "6a9e95e1-bfec-4c7d-9765-360fee313f33",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "def find_missing_number(nums):\n",
    "    n = len(nums) + 1  # Total numbers including the missing one\n",
    "    expected_sum = n * (n + 1) // 2\n",
    "    actual_sum = sum(nums)\n",
    "    return expected_sum - actual_sum\n",
    "\n",
    "# Example usage:\n",
    "nums = [1, 2, 4, 6, 3, 7, 8]\n",
    "print(find_missing_number(nums))  # Output: 5\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8c9b9666-85ef-4621-bfc7-d81fb6ef7c68",
   "metadata": {},
   "source": [
    "Problem 3 : Given an array of n positive numbers. All numbers occurs even number of times except 1 which\n",
    "occurs odd number of times. Find that number in O(n) time and O(1) space. Ex: [1,2,3,2,3,1,3]. 3 is repeats odd\n",
    "times."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "5710c2f0-98ee-498a-9315-b7249cbac3f0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "def find_odd_occurrence(nums):\n",
    "    result = 0\n",
    "    for num in nums:\n",
    "        result ^= num\n",
    "    return result\n",
    "\n",
    "# Example usage:\n",
    "nums = [1, 2, 3, 2, 3, 1, 3]\n",
    "print(find_odd_occurrence(nums))  # Output: 3\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "973a4e7a-1130-406d-9363-1ba179cb3fc0",
   "metadata": {},
   "source": [
    "Problem 4 : Given an array of n elements. Find two elements in the array such that their sum is equal to given\n",
    "element K."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "21869ede-f3ba-46c6-9a9e-3c8773e6e127",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(7, 10)\n"
     ]
    }
   ],
   "source": [
    "def find_pair_with_sum(arr, K):\n",
    "    seen = {}\n",
    "    for num in arr:\n",
    "        complement = K - num\n",
    "        if complement in seen:\n",
    "            return (num, complement)\n",
    "        seen[num] = True\n",
    "    return None\n",
    "\n",
    "# Example usage:\n",
    "arr = [10, 15, 3, 7]\n",
    "K = 17\n",
    "print(find_pair_with_sum(arr, K))  # Output: (7, 10)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "89d72af7-9ac0-43f8-97a1-7ee6d65147dc",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "218b3548-1ce5-4e1a-b514-19416b88da75",
   "metadata": {},
   "source": [
    "Problem 5 : Given an array of both positive and negative numbers, find two numbers such that their sum is\n",
    "closest to 0. Ex: [ 1 ,60 ,-10, 70, -80,85]. Ans : -80,85."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "0f20367e-eaf9-4f93-af45-24ab1c289661",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(-80, 85)\n"
     ]
    }
   ],
   "source": [
    "def find_closest_to_zero_pair(arr):\n",
    "    arr.sort()\n",
    "    left, right = 0, len(arr) - 1\n",
    "    closest_sum = float('inf')\n",
    "    closest_pair = (None, None)\n",
    "    \n",
    "    while left < right:\n",
    "        current_sum = arr[left] + arr[right]\n",
    "        if abs(current_sum) < abs(closest_sum):\n",
    "            closest_sum = current_sum\n",
    "            closest_pair = (arr[left], arr[right])\n",
    "        \n",
    "        if current_sum < 0:\n",
    "            left += 1\n",
    "        else:\n",
    "            right -= 1\n",
    "    \n",
    "    return closest_pair\n",
    "\n",
    "# Example usage:\n",
    "arr = [1, 60, -10, 70, -80, 85]\n",
    "print(find_closest_to_zero_pair(arr))  # Output: (-80, 85)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "90215c9d-d81b-438e-99f6-09d15d6b1bb3",
   "metadata": {},
   "source": [
    "Problem 6 : Given an array of n elements . Find three elements such that their sum is equal to the given\n",
    "number."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "8e5674b1-5504-4ce7-9614-3d617cc28985",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(4, 8, 10)\n"
     ]
    }
   ],
   "source": [
    "def find_three_elements_with_sum(arr, K):\n",
    "    arr.sort()  # Sort the array\n",
    "    n = len(arr)\n",
    "    \n",
    "    for i in range(n - 2):\n",
    "        target = K - arr[i]\n",
    "        left, right = i + 1, n - 1\n",
    "        \n",
    "        while left < right:\n",
    "            current_sum = arr[left] + arr[right]\n",
    "            if current_sum == target:\n",
    "                return (arr[i], arr[left], arr[right])  # Triplet found\n",
    "            elif current_sum < target:\n",
    "                left += 1  # Increase the sum\n",
    "            else:\n",
    "                right -= 1  # Decrease the sum\n",
    "    \n",
    "    return None  # No triplet found\n",
    "\n",
    "# Example usage:\n",
    "arr = [1, 4, 45, 6, 10, 8]\n",
    "K = 22\n",
    "print(find_three_elements_with_sum(arr, K))  # Output: (4, 8, 10)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c0ec05b7-5e96-48a8-aa78-8d03da82c9e4",
   "metadata": {},
   "source": [
    "Problem 7 : Given an array of n elements . Find three elements i, j, k in the array such that\n",
    "i * i + j * j = k*k."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "6269f7bc-26e2-4760-9fdd-97c7cb8c627f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(3, 4, 5)\n"
     ]
    }
   ],
   "source": [
    "def find_pythagorean_triplet(arr):\n",
    "    # Step 1: Square and sort the array\n",
    "    squared_arr = sorted(x**2 for x in arr)\n",
    "    \n",
    "    n = len(squared_arr)\n",
    "    \n",
    "    # Step 2: Fix k^2 and search for i^2 + j^2 = k^2\n",
    "    for k in range(n - 1, 1, -1):  # Iterate from largest to smallest k^2\n",
    "        target = squared_arr[k]  # Assume this is k^2\n",
    "        left, right = 0, k - 1   # Use two pointers\n",
    "        \n",
    "        while left < right:\n",
    "            current_sum = squared_arr[left] + squared_arr[right]\n",
    "            \n",
    "            if current_sum == target:\n",
    "                # Step 3: Return the original triplet (square roots of squared values)\n",
    "                i = int(squared_arr[left]**0.5)\n",
    "                j = int(squared_arr[right]**0.5)\n",
    "                k_value = int(target**0.5)\n",
    "                return (i, j, k_value)\n",
    "            elif current_sum < target:\n",
    "                left += 1  # Increase the sum\n",
    "            else:\n",
    "                right -= 1  # Decrease the sum\n",
    "    \n",
    "    return None  # No triplet found\n",
    "\n",
    "# Example usage:\n",
    "arr = [3, 1, 4, 6, 5]\n",
    "print(find_pythagorean_triplet(arr))  # Output: (3, 4, 5)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7f4740f5-e936-4de2-abef-ce438db35730",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "26371f6e-c19f-4c03-9931-a173a40cdeb4",
   "metadata": {},
   "source": [
    "Problem 8 : An element is a majority if it appears more than n/2 times. Give an algorithm takes an array of n\n",
    "element as argument and identifies a majority (if it exists)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "1bf72150-afb7-4f59-b21a-abfc2f0fa4cc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "def find_majority_element(arr):\n",
    "    # Step 1: Find a candidate\n",
    "    candidate, count = None, 0\n",
    "    for num in arr:\n",
    "        if count == 0:\n",
    "            candidate = num\n",
    "        count += 1 if num == candidate else -1\n",
    "\n",
    "    # Step 2: Verify the candidate\n",
    "    if arr.count(candidate) > len(arr) // 2:\n",
    "        return candidate\n",
    "    return None  # No majority element\n",
    "\n",
    "# Example usage:\n",
    "arr = [2, 2, 1, 1, 2, 2, 2]\n",
    "print(find_majority_element(arr))  # Output: 2\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7ce4fa58-80b4-48ed-9b00-8a32bbee717d",
   "metadata": {},
   "source": [
    "Problem 9 : Given n × n matrix, and in each row all 1’s are followed by 0’s. Find the row with the maximum\n",
    "number of 0’s."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "3b542b33-3781-4362-814d-1390bea25c7b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    }
   ],
   "source": [
    "def find_row_with_max_zeros(matrix):\n",
    "    n = len(matrix)  # Number of rows (and columns, since it's n × n)\n",
    "    max_zeros_row = -1\n",
    "    max_zeros = 0\n",
    "    row, col = 0, n - 1  # Start at the top-right corner\n",
    "\n",
    "    while row < n and col >= 0:\n",
    "        if matrix[row][col] == 0:\n",
    "            # Count all zeros in this row (all columns from current position to 0)\n",
    "            zeros_count = col + 1\n",
    "            if zeros_count > max_zeros:\n",
    "                max_zeros = zeros_count\n",
    "                max_zeros_row = row\n",
    "            col -= 1  # Move left to find more zeros\n",
    "        else:\n",
    "            row += 1  # Move down to the next row\n",
    "\n",
    "    return max_zeros_row\n",
    "\n",
    "# Example usage:\n",
    "matrix = [\n",
    "    [1, 1, 0, 0],\n",
    "    [1, 1, 1, 0],\n",
    "    [1, 0, 0, 0],\n",
    "    [0, 0, 0, 0],\n",
    "]\n",
    "print(find_row_with_max_zeros(matrix))  # Output: 3\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ab8bf0fe-deba-402c-827b-f592f6e47825",
   "metadata": {},
   "source": [
    "Problem 10 : Sort an array of 0’s, 1’s and 2’s [or R’s, G’s and B’s]: Given an array A[] consisting of 0’s, 1’s and\n",
    "2’s, give an algorithm for sorting A[].The algorithm should put all 0’s first, then all 1’s and finally all 2’s at the\n",
    "end. Example Input = {0,1,1,0,1,2,1,2,0,0,0,1}, Output = {0,0,0,0,0,1,1,1,1,1,2,2}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "fa04370f-db18-4d40-8aa8-366a0b92e45e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    }
   ],
   "source": [
    "def find_row_with_max_zeros(matrix):\n",
    "    n = len(matrix)  # Number of rows (and columns, since it's n × n)\n",
    "    max_zeros_row = -1\n",
    "    max_zeros = 0\n",
    "    row, col = 0, n - 1  # Start at the top-right corner\n",
    "\n",
    "    while row < n and col >= 0:\n",
    "        if matrix[row][col] == 0:\n",
    "            # Count all zeros in this row (all columns from current position to 0)\n",
    "            zeros_count = col + 1\n",
    "            if zeros_count > max_zeros:\n",
    "                max_zeros = zeros_count\n",
    "                max_zeros_row = row\n",
    "            col -= 1  # Move left to find more zeros\n",
    "        else:\n",
    "            row += 1  # Move down to the next row\n",
    "\n",
    "    return max_zeros_row\n",
    "\n",
    "# Example usage:\n",
    "matrix = [\n",
    "    [1, 1, 0, 0],\n",
    "    [1, 1, 1, 0],\n",
    "    [1, 0, 0, 0],\n",
    "    [0, 0, 0, 0],\n",
    "]\n",
    "print(find_row_with_max_zeros(matrix))  # Output: 3\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fb9df63f-9c8e-4bd6-b4cd-efca50104586",
   "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}