how to build the hash table in the approach 3. als…
Unknown - Feb 3, 2014
how 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. In that case we will not enter into any for loop.
-Kinshuk
What if there are duplicates in the array? We should keep track of the number of occurrences of each number and update as we go.
Still it work, as we have to just find the sum. If 1 element is in the hashmap, and say other element repeats, we won’t care as their sum will not be equal to given sum T.
I don’t want to find unique pairs,I want all the numbers that form the sum.
eg: array = {5, 6, 7, 4, 1, 3, 2, 8, 9, 10} and T = 15
result:
1+9+5=15
5+10=15
6+4+5=15
2+8+5=15
3+2+6+4=15 … etc
Hi Vikram, this is a different problem all together. Please refer here for the solution - http://codereview.stackexchange.com/questions/56270/list-all-possible-numbers-from-a-given-array-that-sums-up-to-a-given-number.
The hashmap one is a fucking genius. Got excited a bit :x
Thanks Hanyunanodesu :)
The hashmap solution will double print many pairs. How do you handle that?
Hi Anonymous, we will break out of the loop as soon as find the first pair :). Thanks
How to handle if negative & positive numbers exist and T(positive)?
This problem will not occur if you use hashmap, instead of array. But here is a solution via array approach.
Then we can create 2 arrays, hashN and hashP for negative and positive numbers respectively. While inserting, we can have something like hashN[absolute(arr[i])] = arr[i], and TP will fill normally, without absolute i.e. hashP[arr[i]] = arr[i]. Now iterate over the array arr again, and if (arr[i] > T) , then you need negative number, so refer hashN[T-arr[i]], if it exists then you got the number otherwise its a problem. Please let me know if I wasn’t clear enough.
- Kinshuk
hi, i think the last solution also takes O(n^2) you are making hashtable.get operation inside for loop hash table search also has worst case of of O(n) for search operation… so overall it will be O(n^2)
Hi Janardan, creation of hashtable takes O[n] time. Getting a single element in hashtable takes O(1) times, hence as we are in the loop, that takes another O(n) time, hence O(n) as whole. Please let me know if that works for you.
If we use below array({ 2, 6, 8, 4, 5, 7, 3, 9, 1, 5 }) for sum of number 10 - then the first solution will get fail.
The solution is
private static void findPairsForXWay1(int[] pairArray, int x) {
for (int i = 0; i < pairArray.length; i++) {
for (int j = i+1; j < pairArray.length; j++) {
if(pairArray[j] + pairArray[i] == x){
System.out.println("{” + pairArray[i] + “,” + pairArray[j] + “}");
}
}
}
}
Hi The first approach for array({ 2, 6, 8, 4, 5, 7, 3, 9, 1, 5 } ) and sum for number 10 will get fail.The solution for 1st approach is given below.
private static void findPairsForXWay1(int[] pairArray, int x) {
for (int i = 0; i < pairArray.length; i++) {
for (int j = i+1; j < pairArray.length; j++) {
if(pairArray[j] + pairArray[i] == x){
System.out.println("{” + pairArray[i] + “,” + pairArray[j] + “}");
}
}
}
}
Can you please elaborate on the hash map solution. So say I have Key =5 and Value =0. What does that mean. How do I know that it is the answer. Not getting what you mean by “Then as we loop through the array, check each element against the hash table. If the element presents, then print out the key value pair.” Can you please explain with an example?
Hi Chintan, we add all the elements in the array to the hashset. This will take O(n) time and O(n) space of hashmap. Now, iterate over the array, one by one. Now, for each element el in the array, check if K-el exists in the hashmap. If it exists, we have found the solution.