I find an easier non-recursive solution to compute the rectangle number (represented as RN) of an h x w rectangle (which has a height of h units and a width of w units):
Situation 1. if (h and w are coprime) or (h = 1) or (w = 1), then RN = h + w - 1 Situation 2. if h and w are not relatively prime, we can find the greatest common divisor (represented as gcd) that makes (1) h = h' x gcd, w = w' x gcd. and (2) (h' and w' are coprime) or (h' = 1) or (w' = 1). then RN = (h' + w' - 1) x gcd On Aug 23, 8:37 am, Nikhil Jindal <fundoon...@yahoo.co.in> wrote: > Here's my try: > > The following function returns the rectangle number given the dimensions of > the rectangle. > > int FindRectangleNumber(int row, int colm) > { > if (row == colm) > return row; > if (row == 1) > return colm; > if (row%2 == 0 && colm%2 == 0) > return 2*FindRectangleNumber(row/2, colm/2); > if (row%2 == 1 && colm%2 == 0) > return FindRectangleNumber(row - 1, colm) + 2; > if (row%2 == 0 && colm%2 == 1) > return FindRectangleNumber(row, colm - 1) + 2; > if (row%2 == 1 && colm%2 == 1) > return FindRectangleNumber(row - 1, colm-1) + 1; > > } > > This function can be used to solve the given problem. > > On Sun, Aug 22, 2010 at 3:29 PM, Saikat Debnath <saikat....@gmail.com>wrote: > > > > > Can anyone help in finding number of rectangles having a given > > recatngle number. A rectangle number is defined as the number of unit > > sided square formed inside the given rectangle having a common point > > with a diagonal of rectangle. The sides of rectangle have integer > > length. E.g. number of rectangle with rectangle number 4 is 4, i.e. > > 1X4, 2X4, 2X3 and 4X4. > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > Please access the attached hyperlink for an important electronic > communications > disclaimer:http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.