sum

Problem An array contains both positive and negative elements, find the largest subarray whose sum equals 0. Example int[] input = {4, 6, 3, -9, -5, 1, 3, 0, 2} int output = {4, 6, 3, -9, -5, 1} of length 6 Solution Method 1 - Brute force This is simple. Will write later (incomplete) Method 2 - Storing the sum upto ith element in temp array Given an int[] input array, you can create an int[] tmp array where [Read More]

This can be solved efficiently via using HashTables. We can have a hashtable sums sums will store all possible sums of two different elements. For each sum S it returns pair of indexes i and j such that a[i] + a[j] == S and i != j. But initially it’s empty, we’ll populate it on the way. So, this can be done in O(n^2) time. Pseudocode for (int i = 0; i < n; ++i) { // 'sums' hastable holds all possible sums a\[k\] + a\[l\] // where k and l are both less than i for (int j = i + 1; j < n; ++j) { int current = a\[i\] + a\[j\]; int rest = X - current; // Now we need to find if there're different numbers k and l // such that a\[k\] + a\[l\] == rest and k < i and l < i // but we have 'sums' hashtable prepared for that if (sums\[rest\] ! [Read More]

how to build the hash table in the approach 3. als… Unknown - Feb 3, 2014how to build the hash table in the approach 3. also i think you should check if hash(T-arr[i]) is empty first. This comment has been removed by the author. Hi Jianchen, I think we can use hashmap or we can use element as an index in the array. I think only way hash() is empty when the given array is null or has no element. [Read More]

You are given an array of n integers and a target sum T. The goal is to determine whether or not there are two numbers x,y in A with x+y=T. Example : Suppose we have an int array = {5, 3, 7, 0, 1, 4, 2} and T = 5. The unique pairs that sum up to 5 are (5, 0) (3, 2) and (1, 4). There are three approaches to solve this problem - 1) brute force, 2) sort the array and use binary and search, and 3) Using the hashtable. [Read More]