10th_Dec_Sorting_Assignment.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "00d99ae6",
   "metadata": {},
   "source": [
    "# Sorting\n",
    "# Practice Questions\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "77d99d87",
   "metadata": {},
   "source": [
    "# Problem 1.Given an array of n numbers, give an algorithm which gives the element appearing maximum number of times?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "0c0ef017",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "def most_freq_ele(arr):\n",
    "    most_count = 0\n",
    "    most_frequent = None\n",
    "    for num in arr:\n",
    "        count = 0\n",
    "        for other_num in arr:\n",
    "            if num == other_num:\n",
    "                count += 1\n",
    "        if count >= most_count:\n",
    "            most_count = count\n",
    "            most_frequent = num\n",
    "    return most_frequent\n",
    "\n",
    "arr = [1,2,1,1,3,4,5,2,3,1,4,1,9]\n",
    "print(most_freq_ele(arr))\n",
    "\n",
    "\n",
    "## Time complexity: O(n^2): Not efficient"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "571397ab",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "## Better approach\n",
    "##Time complexity: O(n)\n",
    "\n",
    "def find_most_frequent_ele(arr):\n",
    "    frequency_map = {}\n",
    "    # Counting the frequency of each element\n",
    "    for ele in arr:\n",
    "        if ele in frequency_map:\n",
    "            frequency_map[ele] += 1\n",
    "        else:\n",
    "            frequency_map[ele] = 1\n",
    "            \n",
    "    # Finding out the most frequent element\n",
    "    most_count = 0\n",
    "    most_frequent_ele = None\n",
    "    for key, value in frequency_map.items():\n",
    "        if value > most_count:\n",
    "            most_count = value\n",
    "            most_frequent_ele = key\n",
    "            \n",
    "    return most_frequent_ele\n",
    "\n",
    "#example usage:\n",
    "\n",
    "arr = [1,2,1,1,3,4,5,2,3,1,4,1,9]\n",
    "print(find_most_frequent_ele(arr))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "86e12293",
   "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 duplicates in the list. One of the integers is missing in the list. Give an algorithm to find that element Ex: [1,2,4,6,3,7,8] 5 is the missing num."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "9e7f0d3c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The missing element is: 5\n"
     ]
    }
   ],
   "source": [
    "def find_missing_ele(arr):\n",
    "    n = len(arr) + 1\n",
    "    expected_sum = n*(n+1)//2\n",
    "    actual_sum = sum(arr)\n",
    "    missing_ele = expected_sum - actual_sum\n",
    "    return missing_ele\n",
    "\n",
    "arr = [1,2,4,6,3,7,8]\n",
    "print(\"The missing element is:\",find_missing_ele(arr))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f304133f",
   "metadata": {},
   "source": [
    "# Problem 3 : Given an array of n positive numbers. All numbers occurs even number of times except 1 which 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  times."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "a66511d1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "'''\n",
    "the XOR operator works by comparing the bits of two numbers and returning 1 \n",
    "if the bits are different and 0 if the bits are the same\n",
    "'''\n",
    "def find_odd_occurrence(arr):\n",
    "    result = 0\n",
    "    for num in arr:\n",
    "        result ^= num  \n",
    "    return result\n",
    "\n",
    "# Example usage:\n",
    "arr = [1, 2, 3, 2, 3, 1, 3]\n",
    "result = find_odd_occurrence(arr)\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ff071d58",
   "metadata": {},
   "source": [
    "# Problem 4 : Given an array of n elements. Find two elements in the array such that their sum is equal to given element K."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "24117a75",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(7, 3)\n"
     ]
    }
   ],
   "source": [
    "def find_ele(arr, k):\n",
    "    seen = set()\n",
    "    for ele in arr:\n",
    "        complement = k - ele\n",
    "        if complement in seen:\n",
    "            return (ele, complement)\n",
    "        seen.add(ele)\n",
    "    return None\n",
    "\n",
    "#Example usage\n",
    "arr = [1, 3, 5, 6, 7, 8, 3]\n",
    "print(find_ele(arr, 10))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d5d55cd4",
   "metadata": {},
   "source": [
    "# Problem 5 : Given an array of both positive and negative numbers, find two numbers such that their sum is closest to 0. Ex: [ 1 ,60 ,-10, 70, -80,85]. Ans : -80,85."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "66230b11",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Two numbers with sum closest to zero: (-80, 85)\n"
     ]
    }
   ],
   "source": [
    "def closest_numbers_to_zero(arr):\n",
    "    #sort the array\n",
    "    arr.sort()  \n",
    "\n",
    "    left = 0\n",
    "    right = 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",
    "\n",
    "        #Update the closest pair\n",
    "        if abs(current_sum) < abs(closest_sum):\n",
    "            closest_sum = current_sum\n",
    "            closest_pair = (arr[left], arr[right])\n",
    "\n",
    "        #Move pointers\n",
    "        if current_sum < 0:\n",
    "            left += 1\n",
    "        elif current_sum > 0:\n",
    "            right -= 1\n",
    "        else:\n",
    "            break  # If the sum is zero, no need to continue\n",
    "\n",
    "    return closest_pair\n",
    "\n",
    "# Example usage\n",
    "arr = [1, 60, -10, 70, -80, 85]\n",
    "result = closest_numbers_to_zero(arr)\n",
    "print(\"Two numbers with sum closest to zero:\", result)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7c91964",
   "metadata": {},
   "source": [
    "# Problem 6 : Given an array of n elements . Find three elements such that their sum is equal to the given number."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "49367caa",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Three elements with sum 10: (1, 2, 7)\n"
     ]
    }
   ],
   "source": [
    "def find_three_elements(arr, target_sum):\n",
    "    arr.sort()\n",
    "\n",
    "    for i in range(len(arr) - 2):\n",
    "        \n",
    "        left = i + 1\n",
    "        right = len(arr) - 1\n",
    "\n",
    "        while left < right:\n",
    "            current_sum = arr[i] + arr[left] + arr[right]\n",
    "\n",
    "            if current_sum == target_sum:\n",
    "                return arr[i], arr[left], arr[right]\n",
    "            elif current_sum < target_sum:\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "\n",
    "    return None\n",
    "\n",
    "# Example usage\n",
    "\n",
    "arr = [1,2,5,9,6,7]\n",
    "target_sum = 10\n",
    "result = find_three_elements(arr, target_sum)\n",
    "\n",
    "if result:\n",
    "    print(f\"Three elements with sum {target_sum}: {result}\")\n",
    "else:\n",
    "    print(\"No such three elements found.\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d5c55f6b",
   "metadata": {},
   "source": [
    "# Problem 7 : Given an array of n elements . Find three elements i, j, k in the array such that i * i + j * j = k*k."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "001b07b1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Triplet found: (3, 4, 5)\n"
     ]
    }
   ],
   "source": [
    "def find_triplets(arr):\n",
    "    n = len(arr)\n",
    "    for i in range(n):\n",
    "        for j in range(i+1,n):\n",
    "            for k in range(j+1,n):\n",
    "                # Check if i*i + j*j equals k*k\n",
    "                if arr[i] * arr[i] + arr[j] * arr[j] == arr[k] * arr[k] or \\\n",
    "                   arr[j] * arr[j] + arr[k] * arr[k] == arr[i] * arr[i] or \\\n",
    "                   arr[k] * arr[k] + arr[i] * arr[i] == arr[j] * arr[j]:\n",
    "                    return arr[i], arr[j], arr[k]\n",
    "\n",
    "#example usage\n",
    "\n",
    "arr = [1,2,3,4,5]\n",
    "result = find_triplets(arr)\n",
    "if result:\n",
    "    print(\"Triplet found:\",result)\n",
    "else:\n",
    "    print(\"No triplet found!\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4dfe762a",
   "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 element as argument and identifies a majority (if it exists)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "64c09318",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "def find_majority(arr):\n",
    "    n = len(arr)\n",
    "    unique_ele = set()\n",
    "    \n",
    "    for ele in arr:\n",
    "        unique_ele.add(ele)\n",
    "    \n",
    "    for ele in unique_ele:\n",
    "        count = arr.count(ele)\n",
    "        if count > n/2:\n",
    "            return ele\n",
    "\n",
    "arr = [1,2,3,4,5,6,2,3,2,2,2,2,2,2,2,2,2]\n",
    "print(find_majority(arr))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9f3d8043",
   "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 number of 0’s."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "6dd70884",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Row with maximum number of zeros: 2\n"
     ]
    }
   ],
   "source": [
    "def find_row_with_max_zeros(matrix):\n",
    "    max_zeros_row = 0\n",
    "    max_zeros_count = 0\n",
    "\n",
    "    for i in range(len(matrix)):\n",
    "        zeros_count = count_zeros(matrix[i])\n",
    "        if zeros_count > max_zeros_count:\n",
    "            max_zeros_count = zeros_count\n",
    "            max_zeros_row = i\n",
    "\n",
    "    return max_zeros_row\n",
    "\n",
    "def count_zeros(row):\n",
    "    left, right = 0, len(row) - 1\n",
    "\n",
    "    while left <= right:\n",
    "        mid = (left + right) // 2\n",
    "\n",
    "        if row[mid] == 0:\n",
    "            # If the mid element is 0, check for more zeros on the left side\n",
    "            right = mid - 1\n",
    "        else:\n",
    "            # If the mid element is 1, move to the right side\n",
    "            left = mid + 1\n",
    "\n",
    "    return len(row) - left\n",
    "\n",
    "# Example usage\n",
    "matrix = [\n",
    "    [1, 1, 1, 0, 0],\n",
    "    [1, 1, 0, 0, 0],\n",
    "    [1, 0, 0, 0, 0],\n",
    "    [1, 1, 1, 1, 0],\n",
    "    [1, 1, 1, 0, 0]\n",
    "]\n",
    "\n",
    "result = find_row_with_max_zeros(matrix)\n",
    "print(\"Row with maximum number of zeros:\", result)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fb56d2f6",
   "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 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 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": 17,
   "id": "011aaeaf",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original array: [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1]\n",
      "Sorted array: [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2]\n"
     ]
    }
   ],
   "source": [
    "def sort_num(arr):\n",
    "    low, mid, high = 0, 0, len(arr) - 1\n",
    "\n",
    "    while mid <= high:\n",
    "        if arr[mid] == 0:\n",
    "            arr[low], arr[mid] = arr[mid], arr[low]\n",
    "            low += 1\n",
    "            mid += 1\n",
    "        elif arr[mid] == 1:\n",
    "            mid += 1\n",
    "        else:\n",
    "            arr[mid], arr[high] = arr[high], arr[mid]\n",
    "            high -= 1\n",
    "\n",
    "# Example usage\n",
    "arr = [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1]\n",
    "print(\"Original array:\", arr)\n",
    "sort_num(arr)\n",
    "print(\"Sorted array:\", arr)\n"
   ]
  }
 ],
 "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.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}