Thread: Minimum Perimeter of a Rectangle

  1. 07-23-2022 #1
    gawiellus
    gawiellus is offline
    Registered User
    Join Date
    Jun 2019
    Posts
    33

    Minimum Perimeter of a Rectangle

    Hi
    I have to write function that given area as unsigned long long find the minimum perimeter of a rectangle with integer width and length. My code below

    Code:
    typedef unsigned long long ull;


ull minimum_perimeter(ull area) {
  long double a,b;
  for(a = floor(sqrt(area)),b = ceil(sqrt(area));a*b!=area;a--)
  {
    ull b_b=b;
    for(;a*b_b<area;b_b++);
    if(a*b_b==area)
      return 2*(a+b_b);
  }
  return 2*(a+b);
}
    The function did not pass the test due to time out. Can you help me fix the code. Where is mistake, for small numbers alghortim seems to work fine.
    The result can not be square. It is mean that width and length must be different value.
  2. 07-23-2022 #2
    stahta01
    stahta01 is offline
    Registered User
    Join Date
    May 2009
    Posts
    4,183
    You call "sqrt(area)" twice; try calling it just once and assigning it to a local variable. That will only be a minor speedup; but, every little bit helps.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson
  3. 07-23-2022 #3
    Salem
    Salem is offline
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,661
    > Where is mistake, for small numbers alghortim seems to work fine.
    Because the approach of "try all the possible ways" always results in "time limit exceeded" when presenting with larger numbers.

    Which means you need to work smarter, not harder.

    That is, you need to find a better algorithm that does substantially less work.
    Not the first idea that comes into your head.

    The other problem is comparing floating point results using == and !=
    You risk missing actual valid answers due to rounding errors, which are likely for very large numbers.
    Aside from computing the initial square roots, doing all the calculations in integer arithmetic would be my first suggestion.

    Integer factorization - Wikipedia
    Since a square has the minimum possible perimeter, you only need to find the first integer factor of area that's closest to sqrt(area).
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
« Previous Thread | Next Thread »
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Strange issue: Different results of the calculation of a polygn area and perimeter
    By chenb in forum C Programming
    Replies: 3
    Last Post: 12-15-2016, 05:30 AM
  2. Check if the area and perimeter is the expected result
    By chenb in forum C Programming
    Replies: 13
    Last Post: 12-14-2016, 02:12 PM
  3. Triangle Perimeter (nest structure)Issue
    By cc8163 in forum C++ Programming
    Replies: 1
    Last Post: 05-23-2016, 01:52 AM
  4. Program to determine area,perimeter of geometric shapes using coordinates
    By cda67 in forum C Programming
    Replies: 6
    Last Post: 09-29-2011, 04:23 AM
  5. Area Perimeter
    By rossipoo in forum C Programming
    Replies: 5
    Last Post: 11-09-2010, 09:20 PM

Tags for this Thread