practice-geeksforgeeks-arrays.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Rearrange an array with O(1) extra space \n",
    "\n",
    "Given an array arr[] of size N where every element is in the range from 0 to n-1. Rearrange the given array so that arr[i] becomes arr[arr[i]].\n",
    "\n",
    " \n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input:\n",
    "N = 2\n",
    "arr[] = {1,0}\n",
    "Output: 0 1\n",
    "Explanation: \n",
    "arr[arr[0]] = arr[1] = 0.\n",
    "arr[arr[1]] = arr[0] = 1.\n",
    "\n",
    " \n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input:\n",
    "N = 5\n",
    "arr[] = {4,0,2,1,3}\n",
    "Output: 3 4 2 0 1\n",
    "Explanation: \n",
    "arr[arr[0]] = arr[4] = 3.\n",
    "arr[arr[1]] = arr[0] = 4.\n",
    "and so on.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 4, 2, 0, 1]\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    #Function to rearrange an array so that arr[i] becomes arr[arr[i]]\n",
    "    #with O(1) extra space.\n",
    "    def arrange(self,arr, n): \n",
    "        table = arr\n",
    "        a=[]\n",
    "        for i in range(n):\n",
    "            a.append(table[table[i]])\n",
    "        for i in range(n):\n",
    "            arr[i]=a[i]\n",
    "        return arr\n",
    "            \n",
    "        \n",
    "sol = Solution()    \n",
    "print(sol.arrange([4,0,2,1,3],5)) # 3 4 2 0 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Rearrange Array Alternately\n",
    "\n",
    "Given a sorted array of positive integers. Your task is to rearrange  the array elements alternatively i.e first element should be max value, second should be min value, third should be second max, fourth should be second min and so on.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input:\n",
    "N = 6\n",
    "arr[] = {1,2,3,4,5,6}\n",
    "Output: 6 1 5 2 4 3\n",
    "Explanation: Max element = 6, min = 1, \n",
    "second max = 5, second min = 2, and \n",
    "so on... Modified array is : 6 1 5 2 4 3.\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input:\n",
    "N = 11\n",
    "arr[]={10,20,30,40,50,60,70,80,90,100,110}\n",
    "Output:110 10 100 20 90 30 80 40 70 50 60\n",
    "Explanation: Max element = 110, min = 10, \n",
    "second max = 100, second min = 20, and \n",
    "so on... Modified array is : \n",
    "110 10 100 20 90 30 80 40 70 50 60.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[6, 1, 5, 2, 4, 3]\n",
      "[110, 10, 100, 20, 90, 30, 80, 40, 70, 50, 60]\n",
      "[6487, 1969, 6476, 2677, 5748, 3142, 4764, 4631]\n",
      "[4287]\n"
     ]
    }
   ],
   "source": [
    "# 1,2,3,4,5,6\n",
    "# first iteration\n",
    "# 6,1,2,3,4,5\n",
    "#second iteration\n",
    "# 6,1,5,2,3,4\n",
    "#third iteration\n",
    "# 6,1,5,2,4,3\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "        time complexity o(nlogn)\n",
    "        space complexity o(1)\n",
    "    \"\"\"\n",
    "    def rearrange(self,arr, n): \n",
    "        i=0\n",
    "        j=n-1\n",
    "        c=-1\n",
    "        while c<n-2:\n",
    "            for k in range(n-2,c,-1):\n",
    "                arr[k+1],arr[k]=arr[k],arr[k+1]\n",
    "            c=c+2\n",
    "        return arr\n",
    "    \"\"\"\n",
    "    optimized version\n",
    "    \n",
    "    time complexity =o(n)\n",
    "    space complexity = o(n)\n",
    "    \"\"\"\n",
    "    def rearranceOptimized(self,arr,n):\n",
    "        table=[]\n",
    "        i=0\n",
    "        j=n-1\n",
    "        while i<=j:\n",
    "            # table[i]=arr[j]\n",
    "            # table[j]=arr[i]\n",
    "            table.append(arr[j])\n",
    "            table.append(arr[i])\n",
    "            i=i+1\n",
    "            j=j-1\n",
    "        for i in range((len(arr))):\n",
    "            arr[i]=table[i]\n",
    "        return arr    \n",
    "sol = Solution() \n",
    "print(sol.rearranceOptimized([1,2,3,4,5,6],6)) # 6,1,5,2,4,3\n",
    "print(sol.rearranceOptimized([10,20,30,40,50,60,70,80,90,100,110],11)) # 110 10 100 20 90 30 80 40 70 50 60\n",
    "print(sol.rearranceOptimized([1969,2677,3142,4631,4764,5748,6476,6487],8)) # 6487 1969 6476 2677 5748 3142 4764 4631\n",
    "print(sol.rearranceOptimized([4287],1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Count divisors of product of array elements \n",
    "\n",
    "Given an array with N elements, the task is to find the count of factors of a number X which is product of all array elements.\n",
    " \n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input:\n",
    "N = 3\n",
    "Arr[] = {2, 4, 6}\n",
    "Output:\n",
    "10\n",
    "Explanation:\n",
    "2 * 4 * 6 = 48, the factors of 48 are \n",
    "1, 2, 3, 4, 6, 8, 12, 16, 24, 48\n",
    "whose count is 10.\n",
    "\n",
    " \n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input:\n",
    "N = 3\n",
    "Arr[] = {3, 5, 7}\n",
    "Output:\n",
    "8\n",
    "Explanation:\n",
    "3 * 5 * 7 = 105, the factors of 105 are \n",
    "1, 3, 5, 7, 15, 21, 35, 105 whose count is 8."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "8\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def countDivisorsMult(self, a, n):\n",
    "        product = 1\n",
    "        for i in a:\n",
    "            product *=i\n",
    "        count =0\n",
    "        for i in range(1,product+1):\n",
    "            if product % i ==0:\n",
    "                count+=1\n",
    "        return count\n",
    "sol = Solution()    \n",
    "print(sol.countDivisorsMult([2,4,6],3))\n",
    "print(sol.countDivisorsMult([3,5,7],3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Find element occuring once when all other are present thrice \n",
    "\n",
    "Given an array of integers arr[] of length N, every element appears thrice except for one which occurs once.\n",
    "Find that element which occurs once.\n",
    "\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input:\n",
    "N = 4\n",
    "arr[] = {1, 10, 1, 1}\n",
    "Output:\n",
    "10\n",
    "Explanation:\n",
    "10 occurs once in the array while the other\n",
    "element 1 occurs thrice.\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input:\n",
    "N = 10\n",
    "arr[] = {3, 2, 1, 34, 34, 1, 2, 34, 2, 1}\n",
    "Output:\n",
    "3\n",
    "Explanation:\n",
    "All elements except 3 occurs thrice in the array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def singleElement(self, arr, N):\n",
    "        obj = {}\n",
    "        unique=0\n",
    "        for i in arr:\n",
    "            obj[i]=obj.get(i,0)+1\n",
    "        for i in obj:\n",
    "            if(obj[i]==1):\n",
    "                return i\n",
    "sol = Solution()        \n",
    "print(sol.singleElement([3,2,1,34,34,1,2,34,2,1],10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Maximum Index\n",
    "\n",
    "Given an array A[] of N positive integers. The task is to find the maximum of j - i subjected to the constraint of A[i] <= A[j].\n",
    " \n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input:\n",
    "N = 2\n",
    "A[] = {1, 10}\n",
    "Output:\n",
    "1\n",
    "Explanation:\n",
    "A[0]<=A[1] so (j-i) is 1-0 = 1.\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input:\n",
    "N = 9\n",
    "A[] = {34, 8, 10, 3, 2, 80, 30, 33, 1}\n",
    "Output:\n",
    "6\n",
    "Explanation:\n",
    "In the given array A[1] < A[7]\n",
    "satisfying the required \n",
    "condition(A[i] <= A[j]) thus giving \n",
    "the maximum difference of j - i \n",
    "which is 6(7-1)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    #Complete this function\n",
    "    # Function to find the maximum index difference.\n",
    "    def maxIndexDiff(self,arr, n): \n",
    "        i=0\n",
    "        j=n-1\n",
    "        maximum_diff=-1\n",
    "        curr_max_diff=-1\n",
    "        while i<=j:\n",
    "            if arr[i]<=arr[j]:\n",
    "                curr_max_diff= j-i\n",
    "            i+=1\n",
    "            j-=1\n",
    "            if curr_max_diff > maximum_diff:\n",
    "                maximum_diff = curr_max_diff\n",
    "        return maximum_diff\n",
    "sol = Solution()    \n",
    "# print(sol.maxIndexDiff([34, 8, 10, 3, 2, 80, 30, 33, 1],9))\n",
    "#                         0   1   2  3  4   5  6   7   8\n",
    "# print(sol.maxIndexDiff([1,10],2))\n",
    "print(sol.maxIndexDiff([65,6,74,94,56,89,9,63,75,25,34,68,93,48,16],15))\n",
    "#                       0  1  2  3  4 5  6  7  8  9 10 11 12 13 14"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}