Can this solution be optmized?

Question

Given an array say L= [3,4,6,7,2,1] and an Integer Z = 8, find 2 integers X,Y belonging to L such that X + Y = Z

Here is one possible solution -

public static void findIntegersSum(List<Integer> list, int z) {

    for(int i = 0 ;i < list.size(); i++) {
        for(int j = i+1 ; j< list.size(); j++) {
            if(list.get(i) + list.get(j) == z) {
                System.out.println(" X = " + list.get(i) + "\t Y=" + list.get(j));
                return;
            }
        }
    }
    System.out.println(" No match found !!");
}

Question is - Can we optimize the above solution?

http://www.geeksforgeeks.org/write-a-c-program-that-given-a-set-a-of-n-numbers-and-another-number-x-determines-whether-or-not-there-exist-two-elements-in-s-whose-sum-is-exactly-x/ — Diptendu, Mar 19 '15 at 04:27

Shashank · Accepted Answer · 2015-03-19T04:39:08.407

You can do this using an implementation of the Set data type. A Set is most often implemented as either a Hash table (HashSet in Java) or a Binary Search Tree (TreeSet in Java). Hash table implementations often use more memory, but have constant time O(1) lookups and insertions in the average case, tree implementations use linear memory, but have O(log n) lookups and insertions in the average case.

Pseudocode for using this data structure is as follows:

S = set(L) // Iterate through L and put it in a set, O(n) or O(n log n)
for element in L: // O(n)
    if S.has(Z - element): // O(1) or O(log n) depending on HashSet or TreeSet
        X = element
        Y = Z - element
        break

This solution is O(n) or O(n log n) instead of O(n^2).

score 2 · Answer 2 · answered Mar 19 '15 at 04:23

This method can be solved on O(n) time if we are allowed to use additional space of O(R) where R is range of numbers. Here is the implementation

#include <stdio.h>
#define MAX 100000

void printPairs(int arr[], int arr_size, int sum)
{
  int i, temp;
  bool binMap[MAX] = {0}; /*initialize hash map as 0*/

  for(i = 0; i < arr_size; i++)
  {
    temp = sum - arr[i];
    if(temp >= 0 && binMap[temp] == 1)
    {
      printf("Pair with given sum %d is (%d, %d) \n", sum, arr[i], temp);
    }
    binMap[arr[i]] = 1;
  }
}

/* Driver program to test above function */
int main()
{
    int A[] = {1, 4, 45, 6, 10, 8};
    int n = 16;
    int arr_size = 6;

    printPairs(A, arr_size, n);

    getchar();
    return 0;
}

score 0 · Answer 3 · answered Mar 19 '15 at 04:10

0

Sort it, afterwards you only have to iterate over the array once, and check whether the matching value is in the array. This will only be more efficient for big arrays.

answered Mar 19 '15 at 04:10

score 0 · Answer 4 · answered Mar 19 '15 at 04:21

Following solution will be more optimized, as it is reduce List size at every steps.

static void findIntegersSum(List<Integer> list, int z) {
    for(int i = 0 ;i < list.size(); i++) {
        int X = list.remove(i); // Reduce your list
        int Y = z - X;
        if (list.contains(Y)) {
            System.out.println(" X = " + X + "\t Y=" + Y);
            return;
        }
    }
    System.out.println(" No match found !!");
}

Can this solution be optmized?

4 Answers4