Codility MinPerimeterRectangle

Given an integer that represents the area of a rectangle, return the minimal perimeter of a rectangle having that area and integer sides.

You could find and submit your solution to this problem in the Codility Prime and composite numbers section.

It is easy to see that if a rectangle has area 30, its integers sides could only be (1, 30), (2, 15), (3, 10), and (5, 6). The latter giving the minimal perimeter.

My original C++ solution was clumsier than the one you are seeing now. I was checking the input for squares and worse, I started looping from the wrong side. Thanks to the anonymous suggestion below, I have cleaned up my code in this way:
int solution(int input)
{
    assert(input > 0 && input < 1000000001); // 1

    for(int i = static_cast<int>(std::sqrt(input)); i > 0; --i) // 2
    {
        if(input % i == 0) // 3
            return 2 * ((input / i) + i);
    }

    return 0; // 4
}
1. Enforce the problem requirements in the code through an assert.
2. Remembering that among all rectangles having the same area, the square is the one with minimal perimeter, I should start checking from the closest to the optimum down to the minimal rectangle.
3. If the current candidate divides the area with no remainder, it is the best solution. Calculate the perimeter and return it.
4. We should never reach this line. However usually the C++ compilers complain for a missing return value if they don't see it.

2 comments:

  1. #include

    int solution(int N) {
    for(int i=sqrt(N); i!= 0; i--){
    if (N%i == 0){
    return 2*(i+N/i);
    }
    }
    }

    ReplyDelete
    Replies
    1. This is a better solution, I modified my post accordingly. Thank you for contributing.

      Delete