Ugly Numbers

Hey guys, As I promised you few posts ago,
here is my solution for the Ugly numbers question:

#include<stdio.h>

void getUglyNumbersBruteForce(long num )
{
long i,count;
count=0;
long backup;
i=2;

while (count < num )
 {
  backup=i;
  while (i%5==0)i=i/5;
  while (i%3==0)i=i/3;
  while (i%2==0)i=i/2;

  if (i==1)
  {
    printf("%d)The number is: %d\n",count,backup);
    count++;
  }
  i=backup;
  i++;
 }

}

long min3(long num1,long num2,long num3)
{
if ((num1 < num2 ) && (num1 < num3 )) return num1;
if ((num2 < num3 ) && (num2 < num3 )) return num2;
if ((num3 < num2 ) && (num3 < num1 )) return num3;

}

int GetUglyNumbersDynamicProgramming(int num)
{
   long arrayUgly[num];
   long nextNumber,Next2,Next3,Next5;
   int ptrNext2=0;
   int ptrNext3=0;
   int ptrNext5=0;
   int i;
   arrayUgly[0]=1;
   Next2=arrayUgly[0]*2;
   Next3=arrayUgly[0]*3;
   Next5=arrayUgly[0]*5;

   for (i=1;i < num ; i++)
   {
       nextNumber=min3(Next2,Next3,Next5);
       arrayUgly[i]=nextNumber;

       if (nextNumber==Next2)
       {
           ptrNext2++;
           Next2=arrayUgly[ptrNext2]*2;
       }
       if (nextNumber==Next3)
       {
           ptrNext3++;
           Next3=arrayUgly[ptrNext3]*3;
       }
       if (nextNumber==Next5)
       {
           ptrNext5++;
           Next5=arrayUgly[ptrNext5]*5;
       }

       printf("%d)The number is: %d\n",i,arrayUgly[i]);
   }

}

int main()
{

   GetUglyNumbersDynamicProgramming(1500);
   printf("\n\n\n\n\n");
   getUglyNumbersBruteForce(1500);
   return 0;
}

Profiling with gprof for comparing between my Dynamic programming solutions

Profiling with gprof for comparing between my Dynamic programming solutions
Few days ago I have stumble upon an intriguing question, the question goes like this:

We are given a matrix of integers (Positives and negatives) and you should find the max sum of a sub matrix.

of course the sub matrix size can be in the range of size one (single cell) to n x n size.
I have wrote down two solutions,
First I'll explain the methods I have wrote for implementing each algorithm, and after that i'll use gprof  (GNU Profiler) for comparing the algorithms.

So are you ready??? :-)

I have added another matrix for accumulating the sum of each column, so each cell holds the sum of all number above the current cell in the column. of course each cell relies only on a single cell which is above the current one (except the first row which relies on no row at all).
Now I planned to iterate all over the columns while my rectangle starts at row1 and and his height varies along the way, in each iteration an inequality should be satisfied by the following basic property: ( row1+height < n ).

Each time we reach a negative accumulation sum we reinitialize our sum to zero, and each time we reach a higher max sum score we save it.

#define  n 5

void main()
{
 int matrix[][n]={{1,-2,5,16,12},
        {-3,7,9,-17,-13},
              {-4,-9,23,-35,-25},
        {-14,16,19,-21,13},
        {100,12,-5,-5,14}};
 
 int matrixSumColumn[n][n];
 int i,j,row1,column,height,maxSum,sum;


//initializing matrixSumColumn
for (j=0; j < n; j++) matrixSumColumn[0][j]=matrix[0][j];

 for (i=1; i < n; i++)
  for (j=0; j < n; j++) 
    matrixSumColumn[i][j]=matrixSumColumn[i-1][j]+matrix[i][j];  

maxSum=matrix[0][0];
 for (row1=1; row1 < n ; row1++)
 {
  upperCornerY=row1;
  for (height=0;row1+height < n; height++) 
  {
   sum=0;
   upperCornerX=0;
   for (column=0; column < n ;column++)
   {    
    if ((row1!=0)&&(height!=0))
     sum=sum+matrixSumColumn[row1+height][column]-matrixSumColumn[row1-1][column];
    else
     sum=sum+matrixSumColumn[row1+height][column];

    if (sum>maxSum)
    {
     maxSum=sum;
     lowerCornerX=column;   //saving the position of the sub matrix rectangle
     lowerCornerY=row1+height;
    }
    else if (sum<0)
    {
     sum=0;
     upperCornerX=column;

    }
   }
  }//end loop height
   
 }//end loop row1

 printf("sum Columns: \n\n");
 for (i=0; i < n ; i++)
 {
  for (j=0; j < n ;j++) printf("%d ",matrixSumColumn[i][j]);
  printf("\n");
 }

 printf("\nOriginal Matrix:\n\n");
 for (i=0; i < n ; i++)
 {
  for (j=0; j < n ;j++) printf("%d ",matrix[i][j]);
  printf("\n");
 }

 printf("\nThe max summary is: %d, ends at (column number %d, row number %d)\n",maxSum,lowerCornerX,lowerCornerY);
 printf("begins at (column number %d, row number %d)\n\n\n",upperCornerX,upperCornerY);
}