Given an array that we know its size and the range of numbers that can be in it.Find two elements in the array that sum up to a given value.There is a classic version of algorithm which has O(n) as complexity of time and O(K) as the complexity of space using the hash map (K is the range of the integers).What if we want to find DIFFERENT elements that sum up to that given number(for identical elements it does not work).Plus,the program just checks if there is at least one combination and it does not need to find all the possible combinations.
Two different numbers in an array which their sum equals to a given value
539 views Asked by Chad At
3
There are 3 answers
0
On
Search and print the given number sum of elements in array with indexes using python
list1 = [1,2,3,5]
tmp = list1.copy()
print(tmp)
inp = int(input("enter value equal to sum"))
for i in list1:
for j in tmp:
add = i+j
if add == inp:
print (list1.index(i)) #printing the index first val
print (tmp.index(j)) #printing the index second val
print ("value found",add,i,j)
break
#if add ==inp: '''if uncomment this when it found the first occurance it breaks'''
# print("out")
# break
0
On
Here is O(n) solution for finding the first pair of indices of array which sums to the expected target. The solution will stop when it finds the first 2 indices that sum to target, if you need all the pairs that add up to target then instead of using int[] result, you can use ArrayList or even a Map, process the complete array and return it with all the pairs of indices. There is an obvious assumption that the Map's hashcode function is really good and there are not much collisions so that map operations perform in O(1) time.
Adding condition that values of both the indices is not same should provide you solution with different numbers in pair.
import java.util.*;
public class Solution {
public static void main(String[] args) {
int[] array = new int[] {1,2,4,7,12,67,12,5,9,1,10};
System.out.println(Arrays.toString(sum(array, 68)));
}
public static int[] sum(int[] array, int target) {
int[] result = new int[2];
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
// n iterations
for (int index = 0; index < array.length; index++) {
// constant
if (map.containsKey(target - array[index])
&& array[index] != array[map.get(target - array[index])]) {
result[1] = index;
// constant
result[0] = map.get(target - array[index]);
return result;
}
// constant
map.put(array[index], index);
}
return result;
}
}
BST should work.
Step 1 is O(nlogn) Step 2 is O(n/2 logn)