CODEWITHSUNDEEP
calgorithm
Rave
Rave

Reputation: 843

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

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?

Upvotes: 5

Views: 3567

Answers (4)

Petar Ivanov
Petar Ivanov

Reputation: 93030

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

Upvotes: 5

tbert
tbert

Reputation: 2097

You can precompute the "sums" array, put it in size order, and then bsearch(3) the array:

int sums = { /* list of sorted sums */ };

int compare(void *a, void *b) { return ((int *)a - (int *)b); }

if (bsearch((void *)int_to_test, (void *)sums, number_of_items_in_sums, sizeof(int), compare) == NULL)
    errx(1, "not in list!");

printf("found it\n!");

The bsearch syntax is from memory, so double-check that in your man pages.

Upvotes: 0

jimifiki
jimifiki

Reputation: 5534

No need for an hash table!!

You could sort the arrays (one increasing the other one decreasing) and then compare the first elements of the arrays. At each step then move on the first array increasing and on the second decreasing (if the sum is too large you should move on the decreasing array, if the sum too small you have to move on the increasing array)

This algorithm is 2N log(N) + 2 N

Upvotes: 0

user684934
user684934

Reputation:

This is just another formulation of "Find all pairs of elements (a1,b1) such that a1 belongs to Array A and b1 belongs to Array B whose sum a1+b1 = k".

In short, use a hash table.

Upvotes: 0

Related Questions