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?

If the "operand tables" are constant, then you should only need to do a table lookup. The lookup table should contain all possible sums (with no duplicates) and be sorted. Plain binary search to find if a certain sum exists. What algorithm that was used to generate the lookup table itself, is then quite irrelevant. — Lundin, Jan 31 '12 at 09:40

score 5 · Accepted Answer · answered Jan 31 '12 at 07:41

5

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

answered Jan 31 '12 at 07:41

Petar Ivanov

91,536
11
82
95

just to clarify, given a array that is large n, the two for loops are now going to cause the algorithm to become O(n^2) or am i mistaken? – Rave Jan 31 '12 at 08:20
you are mistaken... the loops are not nested. They iterate over the first array and then again over the second. – Petar Ivanov Jan 31 '12 at 08:55
Dear Rave, probably your teacher doesn't want a C++ program. Usually first year students are not taught hashes. Be sure your teacher won't get angry if you use hashes! When I taught a student how to use hashes he was happy to discover a new (simpler) way to solve his problem. But as student if you want to use a set you should write it yourself. And it's not a cake!! – jimifiki Jan 31 '12 at 09:12
Dear petar, I am horribly sorry how I didn't realise this. Dear jimifiki, thank you very much, this is more of independent learning for me, i haven't used C or C++ in a while, so i taught of first brushing up on C and doing some questions. Hopefully i want to practice more problems involved with algorithms. Also thank you so much for your advice above, and the implementation in C++, make sense to me now. I need to write down somewhere that when i see two or more loops check if they are nested or not, i always make that mistake/ – Rave Jan 31 '12 at 13:58

score 0 · Answer 2 · edited May 23 '17 at 12:33

0

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.

edited May 23 '17 at 12:33

Community

1
1

answered Jan 31 '12 at 06:45

honestly, i am not sure how it can be done so easily in a hash table. the pesudo code makes sense, but how will it be implemented in C? – Rave Jan 31 '12 at 06:48

score 0 · Answer 3 · answered Jan 31 '12 at 06:50

0

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

answered Jan 31 '12 at 06:50

jimifiki

5,377
2
34
60

Yes, sorting will solve it in O(nlogn) time, and is an improvement over O(n^2), but is not as good as O(n) time, which a hash table provides. – Jan 31 '12 at 06:52
@jimifiki, i never would of taught of this, i have taken a 0.5 year course on algorithm and we mostly learned about generic algorithms, like dijkstra's, prims, DFS,BFS, etc, and NPC. I am still finding it hard find a optimal algorithms. i would of never taught of using hashtables, is there any tips or secretes that you can tell me to get my self better? – Rave Jan 31 '12 at 06:53
log(N) are not important! Believe me. I just wrote two algorithms (in another contest), one N log N, the other N and the N one is still slower at any N that can fit in my RAM! (Different powers are important, even passing from 2.5 to 2.7 is important, but not logs...). Moreover even hashing should start managing the logarithms at some time (since there is no miracle in cs) – jimifiki Jan 31 '12 at 06:57
Dear Rave,I've said "No need for hash tables".I mean that you don't need this. My suggestion is to find a "sort" routine somewhere in the web, copy paste it and use it.Sorting is a very important algorithm you'll never be able to leave it if you start using it. Hash tables are fine, but they make you lazy. While learning algorithms you should use your mind as much as possible, I suggest you to largely use sort(you already used it for prims, isn't it?) So:while learning programming in C you don't need hashes(unless explicitly asked in your homework), think always in terms of a quicksort. – jimifiki Jan 31 '12 at 07:33
The problem with hash tables in the real world, is the large amount of program overhead, which various "Big O" theories don't take in account. Because of the overhead, it doesn't make sense to implement a hash table unless the amount of data is vast (but when it is, a hash table performs very well). – Lundin Jan 31 '12 at 09:30
`"log(N) are not important!"` I have a problem with the absolutism of that statement. I know it's probably not meant to be an absolute truth, but still I'd prefer to have that explicit. *Usually/most of the time*, a factor of `log N` doesn't matter. Sometimes it does though. And it doesn't repeat well, a factor of `(log N)^2` matters often enough. – Daniel Fischer Jan 31 '12 at 12:40

score 0 · Answer 4 · answered Jan 31 '12 at 06:52

0

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.

answered Jan 31 '12 at 06:52

tbert

2,089
13
14

pre computing the sums mean that i have to compute all possible values, wouldn't that lead me to a O(n^2) runtime, just to compute them? – Rave Jan 31 '12 at 06:56
One-time cost, yes, but you're paying it once instead of every time, for an O(log(n)) runtime. You can't get away from needing to compute the sums somewhere, but saving your work for referencing it later is fine; and if the sums are statically-defined, it's possible the compiler may spare you the cycles by computing the array itself. – tbert Jan 31 '12 at 07:06

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

4 Answers4