# Subarray with Sum k

By | October 29, 2021 ## Problem

Given an unsorted array arr of size N, find a contiguous subarray that adds to a given number k.

## Brute Force Approach

An easy approach is to go through all subarrays one by one and calculate the total of each subarray. The programme that follows implements the basic solution. Run two loops: the outer loop selects a starting point i, while the inner loop attempts all subarrays beginning with i.

This approach will take O(N2) time and O(1) auxiliary space.

## Efficient Approach

The concept is to store the sum of the elements of each prefix of the array in a hashmap, where the key is the sum of each prefix and the index is the most recent index with that sum. So, to see if there is a subarray with a sum equal to k, look at each index I and add up to that index and keep it in the hashmap. Let’s say sum is sum. If a prefix in a hash map has a sum equal to sumk, the subarray with the specified sum is discovered. The steps for algorithm are:

1. Create a hashmap to hold a key-value pair, i.e., key = prefix sum of each prefix and value = its index, and a variable to record the current sum as sum.
2. Traverse through the array.
3. Update the sum for each entry, i.e. sum = sum + array[i].
4. If some prefix has a sum equal to k, display it.
5. If the (sum-k) is found in hashmap, display the subarray with the provided sum.
6. Put sum and current index in the hashmap as a key-value pair.

### C++ Programming

```#include<bits/stdc++.h>
using namespace std;

void subArrayequalsK(int arr[], int n, int k)
{
unordered_map<int, int> mp;

// Maintains prefix sum of elements
int sum = 0;

for (int i = 0; i < n; i++)
{
// add current element to k
sum = sum + arr[i];

// if any prefix sum is equal to target k
if (sum == k)
{
cout << "Found b/w"
<< 0 << " and " << i << endl;
return;
}

// If sum - k already exists in mp
if (mp.find(sum - k) != mp.end())
{
cout << "Found b/w "
<< mp[sum - k] + 1
<< " to " << i << endl;
return;
}

mp[sum] = i;
}
}
int main(){
int a = {1, 3, -4, 2, 5};
int n=sizeof(a)/sizeof(a);
int k =4;
subArrayequalsK(a, n, k);
}```

Output

`Found b/w 0 and 1`

### C# Programming

```using System;
using System.Collections.Generic;
public class Solution
{

public static void subArrayequalsK(int[] arr, int n, int k)
{
int sum = 0;
int begin = 0;
int finish = -1;
Dictionary<int, int> mp = new Dictionary<int, int>();

for (int i = 0; i < n; i++)
{
sum = sum + arr[i];
//check if some prefix sum is equal to k
if (sum == k)
{
begin = 0;
finish = i;
break;
}
// have subarray with the k
if (mp.ContainsKey(sum - k))
{
begin = mp[sum - k] + 1;
finish = i;
break;
}
mp[sum] = i;

}
Console.WriteLine("Found b/w " + begin + " to " + finish);

}
static void Main(string[] args){
int[] arr = {1, 2, 3, 4};
int k = 3;
int n = 4;
subArrayequalsK(arr, n, k);
}
}```

Output

`Found b/w 0 and 1`

### Python Programming

```def subArrayequalsK(arr, n, k):
mp = {}
sum = 0

for i in range(0,n):

# add current element to sum
sum = sum + arr[i]

# if prefix sum is equal to target
if sum == k:

print("Found b/w 1 and", i+1)
return

# If sum - sum already exists in map
if (sum - k) in mp:

print("Found b/w", \
mp[sum - k] + 1, "and", i+1)

return

mp[sum] = i+1

l = [1, 2, 3, 4]
n= len(l)
k = 3
subArrayequalsK(l, n, k)```

Output

```Found b/w 1 and 2
``` 