Lesson 8: MinPerimeterRectangle (Min Perimeter Rectangle)

Lesson 8: MinPerimeterRectangle
https://codility.com/programmers/lessons/8

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). 

This solution can give us the 100% score.

#include <math.h> 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)


Let's think of below.

First we assume 1 <= x < y <= sqrt(N) . Both x and y are integer. (NOTE: this assumes 1 < N, which is a little different from the problem that assume 1 <= N <= 1,000,000,000).

what we want to know is if the following is true.

2 * (y + N / y) < 2 * (x + N / x)

The above can be rewritten as follows.

(y + N / y) < (x + N / x)

(y + N / y) - (x + N / x) < 0

(y - x) + (N / y - N / x) < 0

(y - x) < -(N / y - N / x)

(y - x) < -N / y + N / x

(y - x) < N / x - N / y

(y - x) < Ny - Nx / xy

(y - x) < N(y - x) / xy

1 < N / xy

since 1 <= x < y <= sqrt(N), 0 < xy < N. (even when y is equal to sqrt(N), x is smaller, so xy is always less than sqrt(N) * sort(N) = N.) Then above 1 < N / xy is true.

This means, if N is larger, the perimeter can be minimized when Y is the largest possible value that is less than or equal to sqrt(N)

For N = 1, obviously, there s only value for 'a' such that 1 <= 'a' <= sqrt(N) is 1.

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.

This strategy gives the 100% score, too.

#include <math.h> 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;
}