Software & Finance - Monthly Magazine Online

Volume 2 - Issue 10

October 2012

Technology: Sub Total of Each Pair and Sum


You can find the C++ sample code to find out the sub total for each possible pair in the given array and make sure the sum also exists in the array.

 

Big O notation for finding all possible sum of pairs in a given array is n(n+1) / 2. In our example, it would be 12 elements coming into 78. Comparing whether SUM exists in the array needs to be done with the formula:

 

( (n(n+1) / 2) - n) * n = 792

 

This 792 times can be optimized by using break; statement in the innermost for loop.

 

#include < stdio.h >
#include < string.h >
#include < iostream >
    
void SubTotal_For_Pair_In_Array(int *p, int n)
{
   int count = 0;
   int innercount = 0;
   for(int i = 0; i < n; i++)
   {
      count++;
      int a = p[i];
      for(int j = i + 1; j < n; j++)
      {
         count++;
         int b = p[j];
         int sum = a + b;
         for(int k = 0; k < n; k++)
         {
            innercount++;
            if(sum == p[k])
            {
               std::cout << a << " + " << b << " = " << sum << "\n";
               continue; // Use Break in real time
               //break;
            }
         }
      }
   }
   std::cout << n << " = " << count << "," << innercount << "\n";
}


void main()
{
   int arr[] = { 
      30, 80, 5,  55,
      15, 20, 25, 10,
      60, 65, 70, 75 };

   int len = sizeof(arr) / sizeof(arr[0]);

   SubTotal_For_Pair_In_Array(arr, len);
}

    

 

Sample Output

 

30 + 25 = 55
5 + 55 = 60
5 + 15 = 20
5 + 20 = 25
5 + 25 = 30
5 + 10 = 15
5 + 60 = 65
5 + 65 = 70
5 + 70 = 75
5 + 75 = 80
55 + 15 = 70
55 + 20 = 75
55 + 25 = 80
55 + 10 = 65
15 + 10 = 25
15 + 60 = 75
15 + 65 = 80
20 + 10 = 30
20 + 60 = 80
10 + 60 = 70
10 + 65 = 75
10 + 70 = 80
12 = 78,792
Press any key to continue . . .