8. Tuples, Dictionary And Sets.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "901af222",
   "metadata": {},
   "source": [
    "# Highest frequency number\n",
    "    You are given an array of integers that contain numbers in random order. Write a program to find and return the number which occurs the maximum times in the given input.\n",
    "    If two or more elements contend for the maximum frequency, return the element which occurs in the array first.\n",
    "    Input Format:\n",
    "    The first line of input contains an integer, that denotes the value of the size of the array. Let us denote it with the symbol N.\n",
    "    The following line contains N space separated integers, that denote the value of the elements of the array.\n",
    "    Output Format :\n",
    "    The first and only line of output contains most frequent element in the given array.\n",
    "    Constraints:\n",
    "    0 <= N <= 10^8\n",
    "    Time Limit: 1 sec\n",
    "    Sample Input 1 :\n",
    "    13\n",
    "    2 12 2 11 12 2 1 2 2 11 12 2 6 \n",
    "    Sample Output 1 :\n",
    "    2\n",
    "    Sample Input 2 :\n",
    "    3\n",
    "    1 4 5\n",
    "    Sample Output 2 :\n",
    "    1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2c2312d5",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "from sys import stdin\n",
    "\n",
    "MIN_VALUE=-99999999\n",
    "def maxfreq(test_list):\n",
    "    d={}\n",
    "    for i in test_list:\n",
    "        if i in d:\n",
    "            d[i]+=1\n",
    "        else:\n",
    "            d[i]=1\n",
    "    max=0\n",
    "    maxKey=MIN_VALUE\n",
    "    for i in range(len(test_list)):\n",
    "       \tif d[test_list[i]]>max:\n",
    "            max=d[test_list[i]]\n",
    "            maxKey=test_list[i]\n",
    "    return maxKey\n",
    "\n",
    "\n",
    "def takeInput():\n",
    "    #To take fast I/O\n",
    "    n=int(stdin.readline().strip())\n",
    "    if n==0:\n",
    "        return list(),0\n",
    "    arr=list(map(int,stdin.readline().strip().split( )))\n",
    "    return arr,n\n",
    "\n",
    "arr,n=takeInput()\n",
    "print(maxfreq(arr))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f3303e24",
   "metadata": {},
   "source": [
    "# Maximum Distance\n",
    "    Given an array that might contain duplicate elements, find the maximum possible distance between occurrences of two repeating elements i.e. elements having same value. If there are no duplicate elements in the array, return 0.\n",
    "    Input Format :\n",
    "    Line 1 : Contains integer N which is the size of array\n",
    "    Line 2 : Contains N Integers i.e. the elements of the array.\n",
    "    Sample Output :\n",
    "     Line 1 : Maximum Distance Value\n",
    "    Sample Input :\n",
    "    9\n",
    "    1  3  1  4  5  6  4  8  3\n",
    "    Sample Output :\n",
    "    7\n",
    "    Sample Output Explanation :\n",
    "    arr = [1, 3, 1, 4, 5, 6, 4, 8, 3];\n",
    "        index0 = 1\n",
    "        index1 = 3\n",
    "        index2 = 1\n",
    "        index3 = 4\n",
    "        index4 = 5\n",
    "        index5 = 6\n",
    "        index6 = 4\n",
    "        index7 = 8\n",
    "        index8 = 3\n",
    "\n",
    "        In the above array, the repeating elements are :- (1, 3, 4)\n",
    "        - Distance bw first and last occurence of 1 = 2(index2 - index0)\n",
    "        - Distance bw first and last occurence of 3 = 7(index8 - index1)\n",
    "        - Distance bw first and last occurence of 4 = 3(index6 - index3)\n",
    "\n",
    "        So, for the above array you must return 7, as this is maximum possible distance between two repeating elements having same value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3581b9a4",
   "metadata": {},
   "outputs": [],
   "source": [
    "## Read input as specified in the question.\n",
    "## Print output as specified in the question.\n",
    "def maxDistance(arr, n):\n",
    "     \n",
    "    # Used to store element to first index mapping\n",
    "    mp = {}\n",
    " \n",
    "    # Traverse elements and find maximum distance between\n",
    "    # same occurrences with the help of map.\n",
    "    maxDict = 0\n",
    "    for i in range(n):\n",
    " \n",
    "        # If this is first occurrence of element, insert its\n",
    "        # index in map\n",
    "        if arr[i] not in mp.keys():\n",
    "            mp[arr[i]] = i\n",
    " \n",
    "        # Else update max distance\n",
    "        else:\n",
    "            maxDict = max(maxDict, i-mp[arr[i]])\n",
    " \n",
    "    return maxDict\n",
    "\n",
    "n = int(input())\n",
    "arr = list(map(int,input().split()))\n",
    "print(maxDistance(arr, n))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "850e509a",
   "metadata": {},
   "source": [
    "# Make Unique Array\n",
    "    Find number of elements to be removed to make an array of all distinct elements.\n",
    "    Example:\n",
    "    Ar = {2,1,4,2,1} \n",
    "    output = 2 (remove 2 and 1).\n",
    "    Input format :\n",
    "    Line 1 : Integer N \n",
    "    Line 2 : N integers separated be a single space\n",
    "    Output Format :\n",
    "     Integer\n",
    "    Constraints :\n",
    "     0 <= N <= 10^4\n",
    "    Sample Input :\n",
    "    5\n",
    "    2 1 4 2 1\n",
    "    Sample Output :\n",
    "    2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e953b94b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def duplicateCount(arr):\n",
    "    # Please add your code here\n",
    "    return len(arr) - len(set(arr))\n",
    "        \n",
    "\n",
    "# Main\n",
    "n=int(input())\n",
    "arr=list(int(i) for i in input().strip().split(' '))\n",
    "print(duplicateCount(arr))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ec78cd36",
   "metadata": {},
   "source": [
    "# First non repeating character\n",
    "    In a given string, find the first non-repeating character .You are given a string, that can contain repeating characters. Your task is to return the first character in this string that does not repeat. i.e., occurs exactly once. The string will contain characters only from English alphabet set, i.e., ('A' - 'Z') and ('a' - 'z'). If there is no non-repeating character print the first character of string.\n",
    "    Input Format :\n",
    "    Line 1 : A String , as mentioned above.\n",
    "    Output Format :\n",
    "    First non-repeating character\n",
    "    Sample Input 1 :\n",
    "    aDcadhc\n",
    "    Sample Output 1:\n",
    "    D\n",
    "    Sample Input 2 :\n",
    "    gdhIgHada\n",
    "    Sample Output 2 :\n",
    "    h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aa7efcc9",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "def nonRepeatingChar(string):\n",
    "    # Please add your code here\n",
    "    freq = Counter(string)\n",
    " \n",
    "    # Traverse the string\n",
    "    for i in string:\n",
    "        if(freq[i] == 1):\n",
    "            return i\n",
    "\n",
    "# Main\n",
    "string = input()\n",
    "print(nonRepeatingChar(string))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7d7055e4",
   "metadata": {},
   "source": [
    "# Different Names\n",
    "    In Little Flowers Public School, there are many students with same first names. You are given a task to find the students with same names. You will be given a string comprising of all the names of students and you have to tell the name and count of those students having same. If all the names are unique, print -1 instead.\n",
    "    Note: We don't have to mention names whose frequency is 1.\n",
    "    Input Format:\n",
    "    The only line of input will have a string ‘str’ with space separated first names of students.\n",
    "    Output Format:\n",
    "    Print the names of students along with their count if they are repeating. If no name is repeating, print -1\n",
    "    Constraints:\n",
    "    1 <= |str| <= 10^5\n",
    "    Time Limit: 1 second\n",
    "    Sample Input 1:\n",
    "    Abhishek harshit Ayush harshit Ayush Iti Deepak Ayush Iti\n",
    "    Sample Output 1:\n",
    "    harshit 2\n",
    "    Ayush 3\n",
    "    Iti 2\n",
    "    Sample Input 2:\n",
    "    Abhishek Harshit Ayush Iti\n",
    "    Sample Output:\n",
    "    -10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "af3122ed",
   "metadata": {},
   "outputs": [],
   "source": [
    "def differentNames(l):\n",
    "    # Please add your code here\n",
    "    d={}\n",
    "    for i in l:\n",
    "        if i in d:\n",
    "            d[i]+=1\n",
    "        else:\n",
    "            d[i]=1\n",
    "    return d\n",
    "# Main\n",
    "names=input().strip().split()\n",
    "m=differentNames(names)\n",
    "flag=1\n",
    "for key,val in m.items():\n",
    "    if val>1:\n",
    "        print(key,val)\n",
    "        flag=0\n",
    "if flag==1:\n",
    "    print(-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9259fca4",
   "metadata": {},
   "source": [
    "# Even Count\n",
    "    You are provided with an integer array where each number is present either odd number of times or even number of times. You have to find and return the number which is present even number of times.\n",
    "    If multiple numbers are present even number of times, then return that number which occurs first among these numbers in the given array. If no such number exists, then return -1.\n",
    "    Note : You may take extra space but solve this problem in O(n) time.\n",
    "    Input Format:\n",
    "    Line 1 : An Integer N i.e. size of array \n",
    "    Line 2 : N integers which are elements of the array, separated by spaces\n",
    "    Output Format:\n",
    "    Array element occurring even no. of times\n",
    "    Constraints :\n",
    "    1 <= N <= 10^5\n",
    "    Sample Input:\n",
    "    6\n",
    "    2 5 3 5 3 4 \n",
    "    Sample Output:\n",
    "    \"5. Strings, List & 2D List.ipynb\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0be68bea",
   "metadata": {},
   "outputs": [],
   "source": [
    "def evenCount(arr):\n",
    "    arr_size=len(arr)\n",
    "    for i in range(0,arr_size):\n",
    "        count = 0\n",
    "        for j in range(0, arr_size):\n",
    "            if arr[i] == arr[j]:\n",
    "                count+=1\n",
    "             \n",
    "        if (count % 2 == 0):\n",
    "            return arr[i]\n",
    "         \n",
    "    return -1\n",
    "\n",
    "# Main\n",
    "n=int(input())\n",
    "arr=list(int(i) for i in input().strip().split(' '))\n",
    "print(evenCount(arr))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d777f9db",
   "metadata": {},
   "source": [
    "# Unique triangles\n",
    "    You are given n triangles. You are required to find how many triangles are unique out of given triangles. For each triangle you are given three integers a, b and c (the sides of a triangle).\n",
    "    A triangle is said to be unique if there is no other triangle with same set of sides.\n",
    "    In other words, we have to find frequency of each triangle and return the count of triangles whose frequency is 1.\n",
    "    Note : It is always possible to form triangle with given sides.\n",
    "    Input Constraints :\n",
    "    Line 1 : Integer n, the number of triangles\n",
    "    Next n lines : Three integers a,b,c (sides of a triangle).\n",
    "    Output Format :\n",
    "    print single integer, the number of unique triangles.\n",
    "    Constraints :\n",
    "    1 <= n <= 10^4\n",
    "    1 <= a,b,c <= 10^15.\n",
    "    Sample Input :\n",
    "    5\n",
    "    7 6 5\n",
    "    5 7 6\n",
    "    8 2 9\n",
    "    2 3 4\n",
    "    2 4 3\n",
    "    Sample Output :\n",
    "    1\n",
    "    Explanation:\n",
    "    The answer will be 1, as there is only one triangle with unique set of sides. There are three triangles here: Triangle with sides 2, 3, 4 and Triangle with sides 5, 6, 7 and Triangle with sides 2, 8, 9. The frequency of first two triangles is 2 and the frequency of last triangle is 1. Hence, there is only one triangle with frequency equal to 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "860d03bd",
   "metadata": {},
   "outputs": [],
   "source": [
    "## Read input as specified in the question.\n",
    "## Print output as specified in the question.\n",
    "#Taking Input Using Fast I/O\n",
    "def uniqueTriangle(arr):\n",
    "  row = len(arr)\n",
    "  col = len(arr[0])\n",
    "  mp = {}\n",
    "  hel = {}\n",
    "\n",
    "  for i in range(row):\n",
    "    tri = arr[i]\n",
    "    tri.sort()\n",
    "    strA = [str(x) for x in tri]\n",
    "    strB = ''\n",
    "    strB = strB.join(strA)\n",
    "    if strB not in mp.values():\n",
    "      mp[i] = strB\n",
    "    else:\n",
    "      hel[i] = strB\n",
    "\n",
    "  count = 0\n",
    "  for i in range(row):\n",
    "    if i in mp:\n",
    "      val = mp.get(i)\n",
    "      if val not in hel.values():\n",
    "        count = count + 1\n",
    "\n",
    "  print (count)\n",
    "\n",
    "\n",
    "def takeInput():\n",
    "    # n = int(input())\n",
    "    elements = list(map(int, input().strip().split(\" \")))\n",
    "\n",
    "    return elements\n",
    "\n",
    "# Main.\n",
    "\n",
    "num = int(input())\n",
    "arr=[]\n",
    "for i in range(num):\n",
    "\tarr.append(takeInput())\n",
    "    \n",
    "uniqueTriangle(arr)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0a43a5cb",
   "metadata": {},
   "source": [
    "# Pairs with difference K\n",
    "    You are given with an array of integers and an integer K. You have to find and print the count of all such pairs which have difference K.\n",
    "    Note: Take absolute difference between the elements of the array.\n",
    "    Input Format:\n",
    "    The first line of input contains an integer, that denotes the value of the size of the array. Let us denote it with the symbol n.\n",
    "    The following line contains n space separated integers, that denote the value of the elements of the array.\n",
    "    The following line contains an integer, that denotes the value of K.\n",
    "    Output format :\n",
    "    The first and only line of output contains count of all such pairs which have an absolute difference of K. \n",
    "    Constraints :\n",
    "    0 <= n <= 10^4\n",
    "    Time Limit: 1 sec\n",
    "    Sample Input 1 :\n",
    "    4 \n",
    "    5 1 2 4\n",
    "    3\n",
    "    Sample Output 1 :\n",
    "    2\n",
    "    Sample Input 2 :\n",
    "    4\n",
    "    4 4 4 4 \n",
    "    0\n",
    "    Sample Output 2 :\n",
    "    6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "667ae4c9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def printPairDiffK(l, k):\n",
    "    pairCount = 0\n",
    "    m = {}\n",
    "    for num in l:\n",
    "        if num+k in m:\n",
    "            pairCount += m[num+k]\n",
    "        if k!=0 and num-k in m:\n",
    "            pairCount += m[num-k]\n",
    "\n",
    "        # Update map        \n",
    "        if num in m:\n",
    "            m[num] += 1\n",
    "        else:\n",
    "            m[num] = 1\n",
    "            \n",
    "    return pairCount\n",
    "    \n",
    "# Main\n",
    "n=int(input())\n",
    "l=list(int(i) for i in input().strip().split(' '))\n",
    "k=int(input())\n",
    "print(printPairDiffK(l, k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "841977b8",
   "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.10.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}