Sum of two numbers equal to the given number

Question

I have an array with positive integers in random order. A number x from the list is given ,we need to find any two numbers in the list having sum equal to x.Running time must be less than n^2.

{edit} What I did is that , I put all the numbers less than half of x in one array and greater than half of x in another array and all greater than x are discarded and then the idea is that the required two numbers must from the two arrays (not from a single array) and by iterating I can get the two numbers.

Now for the worst case I am little confuse is that approach is good? or if anyone guide me something more better than this also can we achieve log n or n *log n ?

Answer 1

Your solution is both wrong, and in O(n^2).

1. It is wrong since consider x=5 and arr=[1,2,3,5] - the two numbers needed are from one array, not from both.
   What if arr=[3,3,6], x=6, you will place both 3s in one list (not greater than x/2 for example), and will fail to find 3+3=6.
2. Your algorithm runs in O(n^2), because assume exactly half of the elements are greater than x¹, and half are smaller than x. Then, the number of combinations you have to check are (n/2*n/2) /2 = n^2/8

---

To solve it in O(nlogn), think what happens if you sort the data, given a number arr[i], can you find efficiently if there is a number x-arr[i] in the now sorted array?

You can even enhance the above to O(n) average case by placing the elements in a hash-set, and now, given an number y, can you find efficiently if x-y is also in the set?

EDIT:
Stroked out parts are not relevant anymore since OP editted the question, added a new cause of concern instead.

---

(1) than x/2 in the editted question.

Answer 2

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.

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])) {
                result[1] = index;
                // constant
                result[0] = map.get(target - array[index]);
                return result;
            }
            // constant
            map.put(array[index], index);
        }
        return result;
    }
}

Answer 3

Here you go,

Sort the array using merge sort (Time complexity: n logn). Take two pointers/counters, say i & j, one starts from index 0 and another from n-1 (assuming n size of array is n).

if array[i]+array[j]=sum 
      return;
    else if (array[i]+array[j]<sum) i++;
    else j--;

Do it until i>j.

Overall time complexity: n logn

Answer 4

/* Time Complexity = O(n)-since HashMap operations take O(1) time*/

public static ArrayList<Integer> twoSum(int[] arr , int target){

    if (arr == null){
        throw new IllegalArgumentException();
    }
    ArrayList<Integer> targetHolder = new ArrayList<>();
    HashMap<Integer, Integer> map = new HashMap<>();

    for (int i = 0 ; i < arr.length ; i++){

        if (map.containsKey(arr[i])){
            int index = map.get(arr[i]);
            targetHolder.add(index+1);
            targetHolder.add(i+1);              
        }
        else{
            map.put(target-arr[i], i);              
        }   

    }
    return targetHolder;    
}
public static void main(String[] args) {        
    int[] A = {1,2,3,4,5,6};
    System.out.println(twoSum(A, 6));
}
}

Answer 5

public void function(int[] array, int sum){

     for(int i = 0; i < array.length/2; i ++){
        for(int j = array.length-1;; j--){
            if(array[i]+array[j] < sum) break;
            if(array[i]+array[j] == sum) System.out.println(array[i]+" + "+array[j]+" = "+sum);
        }
    }
}