PROBLEM LINK:
Author: Satyabrat Panda
Tester: Pritish Priyatosh Nayak
Editorialist: Pritish Priyatosh Nayak
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Maths, Number Theory
PROBLEM:
A rectangle with positive integer side length has area X cm^2 and perimeter Y cm. You’re given the value of X + Y. Determine if a rectangle with positive area and positive integer side length is possible for this value.
EXPLANATION:
Assume that the length of the rectangle be a and breadth b.
Let value of X + Y be c.
So,
\implies ab + 2a + 2b = c
\implies 2a + ab + 2b + 4 - 4 = c
\implies a(2 + b) + 2(b + 2) - 4 = c
\implies (a + 2)(b + 2) - 4 = c
\implies (a + 2)(b + 2) = c + 4
The problem boils down to finding two factors of c + 4, i.e , f1 and f2
such that f1 * f2 = c + 4, f1 > 2 and f2 > 2.
Such values of f1 and f2 do not exist if (c + 4) is a prime number or twice a prime number.
So, basically we can loop from 3 to \sqrt N and check if any factor exists.
Time Complexity : O(sqrt(N))