Sliding-window.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sliding-Window"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "700\n",
      "13\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "Max Sum Subarray of size K\n",
    "\n",
    "Given an array of integers and a number K. Write a program to find the maximum sum of a subarray of size K.\n",
    "\n",
    "Input:\n",
    "First line of input contains a single integer T which denotes the number of test cases. Then T test cases follows. First line of each test case contains two space separated integers N and K where N denotes the number of elements. Second line of each test case contains N space separated integers which denotes the elements of the array.\n",
    "Output:\n",
    "For each test case print the maximum sum of a subarray of size K.\n",
    "\n",
    "Constraints:\n",
    "1<=T<=100\n",
    "1<=N<=105\n",
    "1<=K<=N\n",
    "\n",
    "Example:\n",
    "Input:\n",
    "2\n",
    "4 2\n",
    "100 200 300 400\n",
    "9 4\n",
    "1 4 2 10 23 3 1 0 20\n",
    "Output:\n",
    "700\n",
    "39\n",
    "\"\"\"\n",
    "\n",
    "def MaxSumSubarrayofsizeK(nums,k):\n",
    "    wSum = 0\n",
    "    maxSum = 0\n",
    "    for i in range(0,len(nums)-k+1):\n",
    "        wSum = sum(nums[i:i+k])\n",
    "        maxSum = max(wSum,maxSum)\n",
    "    return maxSum\n",
    "        \n",
    "        \n",
    "        \n",
    "print(MaxSumSubarrayofsizeK([100, 200, 300, 400],2))\n",
    "print(MaxSumSubarrayofsizeK([1,9,-1,-2,7,3,-1,2],4))  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'start-position': 3, 'end-position': 4, 'sub-array': [7, 5], 'sumation': 12}\n",
      "{'start-position': 6, 'end-position': 7, 'sub-array': [7, 8], 'sumation': 15}\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "Subarray with given sum\n",
    "\n",
    "Given an unsorted array A of size N of non-negative integers, find a continuous sub-array which adds to a given number S.\n",
    "\n",
    "Input:\n",
    "The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case consists of two lines. The first line of each test case is N and S, where N is the size of array and S is the sum. The second line of each test case contains N space separated integers denoting the array elements.\n",
    "\n",
    "Output:\n",
    "For each testcase, in a new line, print the starting and ending positions(1 indexing) of first such occuring subarray from the left if sum equals to subarray, else print -1.\n",
    "\n",
    "Constraints:\n",
    "1 <= T <= 100\n",
    "1 <= N <= 107\n",
    "1 <= Ai <= 1010\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "def Subarraywithgivensum(nums,s):\n",
    "    for k in range(1,len(nums)):\n",
    "        for i in range(0,len(nums)-k+1):\n",
    "            wSum = sum(nums[i:i+k])\n",
    "            if wSum == s:\n",
    "                return {'start-position':i,'end-position':i+k-1,'sub-array':nums[i:i+k],'sumation':s}\n",
    "    return -1\n",
    "\n",
    "# Subarraywithgivensum([2,3,4,6,8,9],7)\n",
    "print(Subarraywithgivensum([1 ,2, 3, 7, 5],12))\n",
    "print(Subarraywithgivensum([1 ,2, 3, 4, 5, 6, 7, 8, 9, 10],15))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 4, 4, 3]\n",
      "[2, 1]\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "Count distinct elements in every window\n",
    "\n",
    "Given an array A[] of size N and an integer K. Your task is to complete the function countDistinct() which prints the count of distinct numbers in all windows of size k in the array A[].\n",
    "\n",
    "Input:\n",
    "The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains two integers N and K. Then in the next line are N space separated values of the array A[].\n",
    "\n",
    "Output:\n",
    "For each test case in a new line print the space separated values denoting counts of distinct numbers in all windows of size k in the array A[].\n",
    "\n",
    "Constraints:\n",
    "1 <= T <= 100\n",
    "1 <= N <= K <= 105\n",
    "1 <= A[i] <= 105 , for each valid i\n",
    "\n",
    "Example(To be used only for expected output):\n",
    "Input:\n",
    "2\n",
    "7 4\n",
    "1 2 1 3 4 2 3\n",
    "3 2\n",
    "4 1 1\n",
    "\n",
    "Output:\n",
    "3 4 4 3\n",
    "2 1\n",
    "\"\"\"\n",
    "    \n",
    "\n",
    "def MaxSumSubarrayofsizeK(nums,k):\n",
    "    distinctList = []\n",
    "    for i in range(0,len(nums)-k+1):\n",
    "        distinctList.append(len(set(nums[i:i+k])))\n",
    "    return distinctList\n",
    "        \n",
    "        \n",
    "        \n",
    "print(MaxSumSubarrayofsizeK([1 ,2, 1, 3, 4, 2, 3],4)) \n",
    "print(MaxSumSubarrayofsizeK([4 ,1, 1],2)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "Longest subarray with sum divisible by K\n",
    "\n",
    "Given an array containing N integers and a positive integer K. The task is to find the length of the longest sub array with sum of the elements divisible by the given value K.\n",
    "\n",
    "Input:\n",
    "The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case consists of two lines. First line of each test case contains two Integers N and K and the second line contains N space separated elements.\n",
    "\n",
    "Output:\n",
    "For each test case, print the required longest sub array length in new line.\n",
    "\n",
    "Constraints:\n",
    "1<=T<=100\n",
    "1<=N,K<=106\n",
    "-105<=A[i]<=105\n",
    "\n",
    "Example:\n",
    "Input:\n",
    "2\n",
    "6 3\n",
    "2 7 6 1 4 5\n",
    "7 3\n",
    "-2 2 -5 12 -11 -1 7\n",
    "Output:\n",
    "4\n",
    "5\n",
    "\n",
    "Explanation:\n",
    "\n",
    "Input : A[] = {2, 7, 6, 1, 4, 5}, K = 3\n",
    "Output : 4\n",
    "The subarray is {7, 6, 1, 4} with sum 18,\n",
    "which is divisible by 3.\n",
    "\"\"\"\n",
    "\n",
    "def LongestsubarraywithsumdivisiblebyK(nums,sumK):\n",
    "    for k in range(len(nums),0,-1):\n",
    "        for i in range(0,len(nums)-k+1):\n",
    "            wSum = sum(nums[i:i+k])\n",
    "            if wSum % sumK == 0:\n",
    "                return len(nums[i:i+k])\n",
    "    return 0\n",
    "\n",
    "print(LongestsubarraywithsumdivisiblebyK([2 ,7, 6, 1, 4, 5],3))\n",
    "print(LongestsubarraywithsumdivisiblebyK([-2 ,2 ,-5 ,12, -11, -1, 7],3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "yes\n",
      "yes\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "Subarray with 0 sum\n",
    "\n",
    "Given an array a[] of N positive and negative numbers. Find if there is a subarray (of size at-least one) with 0 sum.\n",
    "\n",
    "Input:\n",
    "The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains an integer n denoting the size of the array. The next line contains N space separated integers forming the array.\n",
    "\n",
    "Output:\n",
    "Print \"Yes\" ( without quotes) if there exist a subarray of size at least one with sum equal to 0 or else print \"No\" ( without quotes).\n",
    "\n",
    "Constraints:\n",
    "1 <= T <= 100\n",
    "1 <= N <= 104\n",
    "-105 <= a[i] <= 105\n",
    "\n",
    "Example:\n",
    "Input:\n",
    "2\n",
    "5\n",
    "4 2 -3 1 6\n",
    "5\n",
    "4 2 0 1 6\n",
    "\n",
    "Output:\n",
    "Yes\n",
    "Yes\n",
    "\n",
    "Explanation:\n",
    "Testcase 1: 2, -3, 1 is the subarray with sum 0.\n",
    "\"\"\"\n",
    "\n",
    "def Subarraywith0sum(nums):\n",
    "    for k in range(1,len(nums)):\n",
    "        for i in range(0,len(nums)-k+1):\n",
    "            wSum = sum(nums[i:i+k])\n",
    "            if wSum == 0:\n",
    "                return \"yes\"\n",
    "    return 'no'\n",
    "\n",
    "print(Subarraywith0sum([4, 2, -3, 1, 6]))\n",
    "print(Subarraywith0sum([4 ,2, 0, 1, 6]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "5\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "Longest Sub-Array with Sum K\n",
    "\n",
    "Given an array containing N integers and an integer K. Your task is to find the length of the longest Sub-Array with sum of the elements equal to the given value K.\n",
    "\n",
    "Input:\n",
    "The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case consists of two lines. First line of each test case contains two Integers N and K and the second line contains N space separated elements of the array.\n",
    "\n",
    "Output:\n",
    "For each test case, print the required lenght of the longest Sub-Array in new line. If no such sub array can be formed print 0.\n",
    "\n",
    "Constraints:\n",
    "1<=T<=500\n",
    "1<=N,K<=105\n",
    "-105<=A[i]<=105\n",
    "\n",
    "Example:\n",
    "Input:\n",
    "3\n",
    "6 15\n",
    "10 5 2 7 1 9\n",
    "6 -5\n",
    "-5 8 -14 2 4 12\n",
    "3 6\n",
    "-1 2 3\n",
    "Output:\n",
    "4\n",
    "5\n",
    "0\n",
    "Explanation:\n",
    "TestCase 1:\n",
    "\n",
    "Input : arr[] = { 10, 5, 2, 7, 1, 9 }, \n",
    "K = 15\n",
    "Output : 4\n",
    "The sub-array is {5, 2, 7, 1}.\n",
    "\"\"\"\n",
    "\n",
    "def LongestSubArraywithSumK(nums,sumK):\n",
    "    for k in range(len(nums),0,-1):\n",
    "        for i in range(0,len(nums)-k+1):\n",
    "            wSum = sum(nums[i:i+k])\n",
    "            if wSum == sumK:\n",
    "                return len(nums[i:i+k])\n",
    "    return 0\n",
    "\n",
    "print(LongestSubArraywithSumK([ 10, 5, 2, 7, 1, 9 ],15))\n",
    "print(LongestSubArraywithSumK([ -5 ,8, -14, 2, 4, 12 ],-5))\n",
    "print(LongestSubArraywithSumK([ -1, 2, 3],6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}