Check if a given number is the sum of two numbers from 2 arrays

Question

i tried the brute force way:

#include <stdio.h>

int sum(int a [],int b[], int m);

int main (void)
{
  int a [] = {1,2,3,4,5};
  int b [] = {4,3,5,2,6};
  int i;
  printf("Enter to find a given number:\n");
  scanf("%d",&i);
  printf("%s\n",sum(a,b,i) ? "True":"False");
  return 0;

}

int sum(int a[], int b[],int m)
{
  int i=0,j=0;

  for (i=0;i<=sizeof(a)/sizeof(int)+1;i++)
   for(j=0;j<=sizeof(b)/sizeof(int)+1;j++)
    if (a[i]+b[j]==m)
     return 1;

  return 0;
}

as you can see the run time is O(n^2), are there any clever way to minimise this?

Answer 1

The faster possible solution (O(n)) is to use hash table. Just put all the elements from the first array in it and then while iterating over the second one check if the difference between the target number and the current one is in the hash table. Here is implementation in C++:

int main(){
    int a [5] = {1,2,3,4,5};
    int b [5] = {4,3,5,2,6};
    int m;
    printf("Enter to find a given number:\n");
    scanf("%d",&m);

    set<int> s;
    for (int i = 0; i < 5; i++)
        s.insert(a[i]);

    for (int i = 0; i < 5; i++)
        if (s.count(m-b[i]) > 0) {
            printf("True\n");
            return 0;
        }

    printf("False\n");
}