0 like 0 dislike
249 views
N is the length of array .

1<=N<=1000000

1<=A[i]<=100000

Giving explanation is mandatory , giving code depends on your choice . Also add your name at the bottom of answer so you get the due credits. Direct libraries in python are not allowed to be used as they skip the lagorithm parts sometimes.
in Algorithms and Problems by Expert (15,650 points) | 249 views

4 Answers

0 like 0 dislike
arr=list(map(int,input().split()))  # array as space saperated integers
k=int(input()) # K
n=len(arr)
minn=n
ind=0
lastInd=0
summ=0
while(ind<n):
    summ+=arr[ind]
    if summ==k:
        minn=min(minn,ind-lastInd+1)
    if summ>k:
        while(summ>k):
            summ-=arr[lastInd]
            lastInd+=1
        if summ==k:
            minn=min(minn,ind-lastInd+1)
    ind+=1
print(minn)
by
0 like 0 dislike
//Time = O(n)
//space = O(n)
//we will store the prefix sum as key, and the index as value in a map(index denotes the prefix sum till that point
//we will iterate the array,calculate the prefix sum till that point, if (prefixsum-k) is present in the map, then find the index of prefixsum-k, subtract the current counter and find the minimum length

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,sum=0,k,x,j;
    cin>>n>>k;
    vector<int> a(n);
    map<int,int> mp;
    
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        
    }
    int mx=INT_MAX;
    mp[0]=0;
    for(int i=0;i<n;i++)
    {
    
        sum+=a[i];
        if(mp.find(sum-k)!=mp.end())
        {
            j=mp[sum-k];
            mx=min(mx,i-j);
        }
        mp[sum]=i+1;
    }
    if(mx<n)
        cout<<++mx;
    else
        cout<<" no subarray where sum= k";
}
by
0 like 0 dislike

Approach :

  1. Used Two pointer i.e i and j  
  2. j pointer is used to add an upcoming event and I pointer is used for removing the initial valued element if my sum goes out of range of targets.

Complexity

  • Time Complexity : O(n*n)
  • Space complexity: O(1)
import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
    // smallest subarray with sum K
    public static int subArraylen(int arr[], int n, int k)
    {
        int sumsofar = 0;
        int i=-1,j=-1,indexi=0,indexj=0;
        int minlen  = Integer.MAX_VALUE;
        while(i<arr.length && j<arr.length) {
            if(i==-1 && j==-1) {
                i=0;
                j=0;
            }
            sumsofar+=arr[j];
            while(sumsofar > k) {
                sumsofar-=arr[i];
                i++;
            }
            if(sumsofar == k) {
                minlen =Math.min(minlen, j-i+1);
                indexi=i;
                indexj=j;
            }
            j++;
        }
        return minlen;
    }
    public static void main(String[] args)
    {
        int arr[] = { 11, 22, 23, 41,12,12,32,13,23,24,24,2,1,2,2,3,4 };
        int n = arr.length;
        int K = 7;
        int len = subArraylen(arr, n, K);
        if (len == Integer.MAX_VALUE)
        {
            System.out.println("Subarray doesnt exits");
        }
        else
        {
            System.out.println("len ="+len + "\n");
        }
    }
    }
by Expert (720 points)
edited by
0 like 0 dislike
Basically, you were told to find a subarray in an array whose sum is k .

Solution : Create prefix sum of the array . pref[i] means a[1]+a[2]+a[3]+....a[i].    Now, say you are at index 'i' , and pref[i]-k did occur as a prefix sum earlier..it means you have found a subarray with sum equal to "k" . You can store all pref[i] in a hashmap to do the easy lookup.  Shortest subarray can be selected by knowing the last index which had sum : pref[i]-k , in the hashmmap during lookup .
by