Skip to main content

Find all subarray with given sum

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 )




Comment

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