 # PROBLEM LINK:

Practice

Contest

Author: Satyabrat Panda

Tester: Pritish Priyatosh Nayak

Editorialist: Pritish Priyatosh Nayak

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

1 Like