[ayad001]

/*Using any programming language you like, but without using advanced library functions:

Given an array of integers, count how many times any contiguous sequence of three numbers in the array adds up to the number '24'.

For example, in the following sequence:

8 9 7 4 5 6 11 13 0 4 8

The answer would be: 2, because "8 9 7" adds up to 24 and "11 13 0" adds up to 24.

and, in the following sequence:

12 6 6 8 10 5 4 15 2 7 10

The answer would be: 4.


i have tried to unroll the loops for optimization, my question IS THAT HOW CAN I EFFICIENTLY MAKE SURE THAT SUM DOESN'T OVERFLOW,. ???

thanks


*/

#include <stdlib.h>
#include <stdio.h>
#define BLOCKSIZE (4) //depends on machine cache size



unsigned int contiguousSum(const int* , int);//pointer to a constant int indicates to the compiler
                                             //that the array values will not be changed and so it 
                                             //does not need to reload/store values in memory and
                                             //the data can be stored in the cache

int main(int argc, char *argv[])
{
    
      
      int i,n;
      int * array1;
      printf ("Amount of numbers to be entered: ");
      scanf ("%d",&i);
      array1 = (int*) calloc (i,sizeof(int));
      if (array1==NULL) exit (1);
      for (n=0;n<i;n++)
      {
        printf ("Enter number #%d: ",n);
        scanf ("%d",&array1[n]);
      }                            
      printf("\ncount is: %d", contiguousSum(array1,i));
      free (array1);     
    getch();
                               
    return 0;
    
        
}

unsigned int contiguousSum(const int* array1, int n)
{
    
  int sum = 0, i, limit = (n-3)/BLOCKSIZE*BLOCKSIZE + 3;// limit is used to loop through array, but 
                                                        // only upto the point where it divides exactly
                                                        // into BLOCKSIZE                       
  unsigned int count = 0;                             
  
  if (array1 == NULL )
     return count;  
  
  sum = array1[0]+ array1[1]+ array1[2];
  
  if (sum == 24)
     count++;    
                     
  for(i=3 ;i<limit;i+= BLOCKSIZE) //unrolling loop to reduce the number of times the 
                                  //for loop conditions are checked.
  {
     sum += array1[i] - array1[i-3];
     if (sum == 24)
        count++;       
     sum += array1[i+1] - array1[i-2];
     if (sum == 24)
        count++;
     sum += array1[i+2] - array1[i-1];
     if (sum == 24)
        count++;
     sum += array1[i+3] - array1[i];
     if (sum == 24)
        count++;   
          
  }
  
  for(;i<n;i++)
  {
     sum += array1[i] - array1[i-3];
     if (sum == 24)
        count++;                           
  }
  return count;   
    
}