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

Question

I tried brute force method:

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

since you can see that the runtime is O (n ^ 2), is there any smart way to minimize this?

Answer 1

A faster solution ( O(n) ) is to use a hash table. Just put all the elements from the first array into it, and then iterate over the second, check if the difference between the target number and the current one in the hash table is. Here is the 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(mb[i]) > 0) { printf("True\n"); return 0; } printf("False\n"); } 

Answer 2

This is just another wording "Find all pairs of elements (a1, b1) for which a1 belongs to Array A and b1 belongs to Array B, the sum of which is a1 + b1 = k . "

In short, use a hash table.

Answer 3

No need for a hash table!

You can sort the arrays (one magnifying the other) and then compare the first elements of the arrays. At each step, move through the first array, and at the second, decrease (if the amount is too large, you must move in a decreasing array, if the amount is too small, you need to move in an increasing array)

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

Answer 4

You can pre-copy the "sums" array, place it in size order, and then bsearch (3):

 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 this on your pages.