c program

Hi i am writing a c program to check for the number of A+B=C relationships in an input array where A, B and C are 3 distinct elements in the array. Lets say the user is to input two lines. The first line is the number of integer elements he wish to enter, the second line is the integer elements in the array.

So far , my method is:
1) Assign the user input to input[size] where size is specified by the user.
2) Next , i will add input[0] to input[1] and then input[0] to input[2], then input[0] to input[3] and so on till the size specified by user. I will then continue the same procedure of adding input[1] to input[2],input[1] to input [3] till the size entered by user.You get the idea.
Subsequently, i will check the sum of each result and match it with the remaining elements in the array. If there is a match, then counter++.

I cant get my code to work though, i need help.
Or can someone suggest a better method .. Thanks a million.

Code:

---

/* This program caluclates the number of relations in the form  A + B= C, given the user input of number of elements and arrary content*/

#include<stdio.h>
#define SIZE 100
int main()
{
    int input[SIZE],A[SIZE],B[SIZE],size,i,n=0,sum=0,counter_plus=0,k=0;


    printf("Please enter the number of integers in your selection: ");
    scanf("%d",&size);
    printf("\n");
    printf("Please enter your integers: ");


    for(i=0;i<size;i++)
   
        scanf("%d",&input[i]); //initialise the arrays
   
    while(k<size)
    {
    for(i=0;i<size;i++)
    {
       
        sum=input[k]+input[i+1];
        if(i==size-1)// means it has reached the end of the seq of numbers
        ++k;
        while(n<size)
        {
            if(sum==input[n])//check if the sum obtained is equal to any of the numbers in the seq
            {
                ++counter_plus;
                break;
            }
            ++n;
        }
    }
    }


    printf("%d",counter_plus);

  return 0;
}

---

There is a (much) more efficient way to do this.

Say the user input 3 and 5. You need to only start check in the sorted sums, for an 8.

That 8 could be found by a binary search, an indexed search, etc., but the very fastest way would be to have an array where all the sums values were assigned to the [index], of a second array.

Say it was called mysums[]. If mysums[8] was set to zero when mysums[] was created, and now mysums[8] has a value (of 8 or 1, just something other than zero), then your program would know that there was a sum with the value of 8, in the array of data the user entered.

User data: 3 + 12 + 5... sum[20] equals 1 or any nonzero value. Now:

Code:

---

if(mysums[sum])
  printf("Matching sum was found.\n");
else
  printf("No matching sum was found.\n");

---

Now the search, is reduced to checking just one value. This technique is the basis for an algorithm called "Counting Sort", btw. You can't always use it (negative numbers, really big numbers, floating point numbers), but when you can use it, it's VERY fast, indeed.

Do you want to change it to use counting sort, or stick with the first way you were trying to do it? Counting sort is pretty simple once you wrap your head around the concept.

And Welcome to the forum, Yong Jie! ;)

Quote:

---

Originally Posted by Adak

There is a (much) more efficient way to do this.

Say the user input 3 and 5. You need to only start check in the sorted sums, for an 8.

That 8 could be found by a binary search, an indexed search, etc., but the very fastest way would be to have an array where all the sums values were assigned to the [index], of a second array.

Say it was called mysums[]. If mysums[8] was set to zero when mysums[] was created, and now mysums[8] has a value (of 8 or 1, just something other than zero), then your program would know that there was a sum with the value of 8, in the array of data the user entered.

User data: 3 + 12 + 5... sum[20] equals 1 or any nonzero value. Now:

Code:

---

if(mysums[sum])
  printf("Matching sum was found.\n");
else
  printf("No matching sum was found.\n");

---

Now the search, is reduced to checking just one value. This technique is the basis for an algorithm called "Counting Sort", btw. You can't always use it (negative numbers, really big numbers, floating point numbers), but when you can use it, it's VERY fast, indeed.

Do you want to change it to use counting sort, or stick with the first way you were trying to do it? Counting sort is pretty simple once you wrap your head around the concept.

And Welcome to the forum, Yong Jie! ;)

---

Thanks a lot for the recommendation. Maybe i will try this method..:cool:

Maybe you should. Cool indeed! ;)