Codility: Lesson 8: MinPerimeterRectangle (Min Perimeter Rectangle)

Codility and other programming lessons: Lesson 8: MinPerimeterRectangle (Min Perimeter Rectangle)

An integer N is given, representing the area of some rectangle.

The area of a rectangle whose sides are of length A and B is A * B, and the perimeter is 2 * (A + B).

The goal is to find the minimal perimeter of any rectangle whose area equals N. The sides of this rectangle should be only integers.

For example, given integer N = 30, rectangles of area 30 are:

• (1, 30), with a perimeter of 62,
• (2, 15), with a perimeter of 34,
• (3, 10), with a perimeter of 26,
• (5, 6), with a perimeter of 22.

Write a function:

int solution(int N);

that, given an integer N, returns the minimal perimeter of any rectangle whose area is exactly equal to N.

For example, given an integer N = 30, the func

The simplest solution is to check all the possible values for a and b.
Yet, since a * b = N, we only have to check the values less than sqrt(N). 
int solution(int N)
{      int a;
    int sqrtN = sqrt(N);      int min = 2147483647; //the initial value for the min (INT_MAX).
    for (a = 1; a <= sqrtN; a++){          if (N % a == 0){
            int b = N / a;
            min = a + b < min ? a + b : min;
        }
    }
    return min * 2; }

However, the above code is not very efficient.

It is better to check the value of a, decrementing from sqrt(N) to 1, and finish checking right when we find some value for 'a' that is N % a == 0, and return (a * N / a) * 2. (note that N / a = b)
So we always can start checking from the integer value 'a' from the sqrt(N) to 1 and when we met the first value that has the integer value 'b', which is b = N % a, the 'a' and 'b' gives the minimum value.
int solution(int N)
{      int a;
    int sqrtN = sqrt(N);

    for (a = sqrtN; a >= 1; a--){
        if (N % a == 0){
            break;
        }
    }

    return (a + N / a) * 2;
}
http://rafal.io/posts/codility-min-perimeter-rectangle.html

public int solution(int N) {
  int minPer = Integer.MAX_VALUE;

  for(int i = 1; i*i <= N; i++){
    if(N % i == 0){
      minPer = Math.min(minPer, 2*(N/i + i));
    }
  }

  return minPer;
}

Read full article from Codility and other programming lessons: Lesson 8: MinPerimeterRectangle (Min Perimeter Rectangle)