Two different numbers in an array which their sum equals to a given value

Question

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.

Answer 1

BST should work.

1. Sort the array into a BST.
2. While (current node is not root, perform inorder traversal)
   • For current node, check:
   • If the sum is greater than the current value
   • If there is an item in the array that satisfies the sum criteria
   • Make the next item in inorder traversal the current node

Step 1 is O(nlogn) Step 2 is O(n/2 logn)

Answer 2

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

Answer 3

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;
    }
}