Find all subarray with given sum
Here given code implementation process.
/*
Java program
Find all subarray with given sum
*/
import java.util.*;
import javafx.util.Pair;
public class SubArraySum
{
// Returns absolute difference of given sum and k
private int difference(int sum, int k)
{
if (sum >= k)
{
return sum - k;
}
else if (sum >= 0)
{
return -(k - sum);
}
else
{
return k + sum;
}
}
// This function are finding all the subarray with given sum
public void ksumSubarray(int[] arr, int k)
{
// Define map with list of Integer elements
HashMap < Integer, List < Integer >> map = new HashMap < > ();
// Define list with integer pair value
List < Pair < Integer, Integer >> result = new ArrayList < Pair < Integer, Integer >> ();
// Get the size of array
int size = arr.length;
// Define auxiliary variable which is calculate sum and difference
int sum = 0, diff = 0;
// iterate loop through by given array size
for (int i = 0; i < size; ++i)
{
sum += arr[i];
if (sum == k)
{
// Base case index 0 to i sum is k
result.add(new Pair < Integer, Integer > (0, i));
}
// Find the difference between the current sum and the given k.
diff = difference(sum, k);
if (map.containsKey(diff))
{
//When current sum difference already exist in map collection
for (int record: map.get(diff))
{
//Add new pair into resultant pair
//record+1 is next index of exist sum
result.add(new Pair < Integer, Integer > (record + 1, i));
}
}
if (map.containsKey(sum))
{
map.get(sum).add(i);
}
else
{
map.put(sum, new ArrayList < Integer > ());
map.get(sum).add(i);
}
}
// Display given sum
System.out.println(" Subarray of sum " + k + " are ");
if (result.size() == 0)
{
// In case there are no subarray pair of given k
System.out.println("None");
}
else
{
// Display resultant index
for (Pair data: result)
{
System.out.println(" Index location (" + data.getKey() + " " + data.getValue() + ")");
}
}
}
public static void main(String[] args)
{
SubArraySum task = new SubArraySum();
//Array element
int[] arr = {
5 , 3 , 2 , -3 , 3 , 8 , -8 , 6 , 4 , -8
};
// k = 10
// Find subarray with given sum
task.ksumSubarray(arr, 10);
}
}input
Subarray of sum 10 are
Index location (0 2)
Index location (0 4)
Index location (2 5)
Index location (0 6)
Index location (3 8)
Index location (5 8)
Index location (7 8)// Include header file
#include <iostream>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
class SubArraySum
{
public:
// Returns absolute difference of given sum and k
int difference(int sum, int k)
{
if (sum >= k)
{
return sum - k;
}
else if (sum >= 0)
{
return -(k - sum);
}
else
{
return k + sum;
}
}
// This function are finding all the subarray with given sum
void ksumSubarray(int arr[], int k, int size)
{
// Define map with list of Integer elements
unordered_map < int, vector < int > > map;
// Define list with integer pair value
vector < pair < int, int > > result;
// Define auxiliary variable which is calculate sum and difference
int sum = 0;
int diff = 0;
// iterate loop through by given array size
for (int i = 0; i < size; ++i)
{
sum += arr[i];
if (sum == k)
{
// Base case index 0 to i sum is k
result.push_back(make_pair(0, i));
}
// Find the difference between the current sum and the given k.
diff = this->difference(sum, k);
if (map.find(diff) != map.end())
{
//When current sum difference already exist in map collection
for (auto &it : map[diff])
{
//Add new pair into resultant pair
//record+1 is next index of exist sum
result.push_back(make_pair( it + 1, i));
}
}
if (map.find(sum) != map.end())
{
map[sum].push_back(i);
}
else
{
map[sum].push_back(i);
}
}
// Display given sum
cout << " Subarray of sum " << k << " are " << endl;
if (result.size() == 0)
{
// In case there are no subarray pair of given k
cout << "None" << endl;
}
else
{
// Display resultant index
for (auto data = result.begin(); data != result.end(); data++)
{
cout << " Index location (" << data->first
<< " " << data->second << ")" << endl;
}
}
}
};
int main()
{
SubArraySum *task = new SubArraySum();
//Array element
int arr[] =
{
5 , 3 , 2 , -3 , 3 , 8 , -8 , 6 , 4 , -8
};
// Get the size of array elements
int size = sizeof(arr) / sizeof(arr[0]);
// k = 10
// Find subarray with given sum
task->ksumSubarray(arr, 10, size);
return 0;
}input
Subarray of sum 10 are
Index location (0 2)
Index location (0 4)
Index location (2 5)
Index location (0 6)
Index location (3 8)
Index location (5 8)
Index location (7 8)// Include namespace system
using System;
using System.Collections.Generic;
public class SubArraySum
{
// Returns absolute difference of given sum and k
private int difference(int sum, int k)
{
if (sum >= k)
{
return sum - k;
}
else if (sum >= 0)
{
return -(k - sum);
}
else
{
return k + sum;
}
}
// This function are finding all the subarray with given sum
public void ksumSubarray(int[] arr, int k)
{
// Define map with list of Integer elements
Dictionary < int, List < int >> map = new Dictionary <int, List < int >> ();
// Define list with integer pair value
List < Tuple < int, int >> result = new List < Tuple < int, int >> ();
// Get the size of array
int size = arr.Length;
// Define auxiliary variable which is calculate sum and difference
int sum = 0;
int diff = 0;
// iterate loop through by given array size
for (int i = 0; i < size; ++i)
{
sum += arr[i];
if (sum == k)
{
// Base case index 0 to i sum is k
result.Add(new Tuple < int, int > (0, i));
}
// Find the difference between the current sum and the given k.
diff = this.difference(sum, k);
if (map.ContainsKey(diff))
{
//When current sum difference already exist in map collection
foreach(int record in map[diff])
{
//Add new pair into resultant pair
//record+1 is next index of exist sum
result.Add(new Tuple < int, int > (record + 1, i));
}
}
if (map.ContainsKey(sum))
{
map[sum].Add(i);
}
else
{
map.Add(sum, new List < int > ());
map[sum].Add(i);
}
}
// Display given sum
Console.WriteLine(" Subarray of sum " + k + " are ");
if (result.Count == 0)
{
// In case there are no subarray pair of given k
Console.WriteLine("None");
}
else
{
// Display resultant index
for (int i = 0; i < result.Count; i++)
{
Console.WriteLine(" Index location ({0} {1})",
result[i].Item1, result[i].Item2);
}
}
}
public static void Main(String[] args)
{
SubArraySum task = new SubArraySum();
//Array element
int[] arr = {
5 , 3 , 2 , -3 , 3 , 8 , -8 , 6 , 4 , -8
};
// k = 10
// Find subarray with given sum
task.ksumSubarray(arr, 10);
}
}input
Subarray of sum 10 are
Index location (0 2)
Index location (0 4)
Index location (2 5)
Index location (0 6)
Index location (3 8)
Index location (5 8)
Index location (7 8)<?php
/*
PHP Program
Find all subarray with given sum
*/
class Hashing
{
// Returns absolute difference of given sum and k
public
function difference($sum, $k)
{
if ($sum >= $k)
{
return $sum - $k;
}
else if ($sum >= 0)
{
return -($k - $sum);
}
else
{
return $k + $sum;
}
}
// This function are finding all the subarray with given sum
public
function subarray_sum($arr, $k)
{
$dict_item = array();
$result = array();
// Define auxiliary variable which is calculate sum and difference
$sum = 0;
$diff = 0;
// Get the size of array
$size = count($arr);
// iterate loop through by given array size
for ($i = 0; $i < $size; ++$i)
{
// Calculate current sum
$sum += $arr[$i];
if ($sum == $k)
{
// Base case index 0 to i sum is k
$result[] = array(0, $i);
}
$diff = $this->difference($sum, $k);
if (array_key_exists($diff, $dict_item))
{
for ($j = 0; $j < count($dict_item[$diff]); $j++)
{
$result[] = array($dict_item[$diff][$j] + 1, $i);
}
}
if (array_key_exists($sum, $dict_item))
{
array_push($dict_item[$sum], $i);
}
else
{
$dict_item[$sum] = array($i);
}
}
// Display Given k sum
echo " Subarray of sum ".$k.
" are\n";
if (count($dict_item) == 0)
{
// In case there are no subarray pair of given k
}
else
{
// Display resultant index
foreach($result as $key => $value)
{
echo " Index location ($value[0] $value[1]) \n";
}
}
}
}
function main()
{
$obj = new Hashing();
// Define array of integer elements
$arr = array(5, 3, 2, -3, 3, 8, -8, 6, 4, -8);
// k = 10
// Find subarray with given sum
$obj->subarray_sum($arr, 10);
}
main();input
Subarray of sum 10 are
Index location (0 2)
Index location (0 4)
Index location (2 5)
Index location (0 6)
Index location (3 8)
Index location (5 8)
Index location (7 8)# Python program
# Find all subarray with given sum
class Hashing:
# Returns absolute difference of given sum and k
def difference(self,amount, k) :
if(amount >= k ) :
return amount-k
elif(amount >= 0) :
return -(k - amount)
else :
return k + amount
# This function are finding all the subarray with given sum
def subarray_sum(self,collection,k):
dictItem = {}
result = []
# Define auxiliary variable which is calculate sum and difference
amount = 0
diff = 0
# iterate loop through by given array size
for i, val in enumerate(collection):
# Calculate current sum
amount += val
if(amount==k):
result.append([0,i])
# Find the difference between the current sum and the given k.
diff=self.difference(amount,k)
if diff in dictItem:
# When current sum difference already exists in dictionary collection
for record in dictItem[diff]:
# Add new pair
result.append([record+1,i])
if amount in dictItem :
dictItem[amount].append(i)
else:
dictItem[amount]=[i]
# Display given sum
print(" Subarray of sum ",k," are")
if len(result) == 0:
# In case there are no subarray pair of given k
print("None")
else :
# Display resultant index
for record in result:
print(" Index location (",record[0],"",record[1],")")
def main():
obj = Hashing()
# Define list element
item =[5, 3, 2,-3, 3, 8, -8, 6, 4, -8]
# k = 10
# Find subarray with given sum
obj.subarray_sum(item,10)
if __name__=="__main__":
main()input
Subarray of sum 10 are
Index location ( 0 2 )
Index location ( 0 4 )
Index location ( 2 5 )
Index location ( 0 6 )
Index location ( 3 8 )
Index location ( 5 8 )
Index location ( 7 8 )
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment