Problem Link - Farmer And His Plot Practice Problem in Basic Math
Problem Statement:
Santosh has a rectangular plot of land, and he wants to divide it into the minimum number of square plots such that:
- All the squares have the same area.
- The squares perfectly divide the rectangular land (without leaving any remainder).
The goal is to determine the minimum number of square plots required for each test case.
Approach:
- The largest square that can be used to divide the rectangular land will have sides equal to the greatest common divisor (GCD) of the length (
N) and breadth (M) of the rectangle.- This is because the GCD gives the largest possible square size that can divide both dimensions perfectly.
- Once the size of the square is determined (which is
GCD(N, M)), the number of square plots is simply the area of the rectangle divided by the area of the square. - For calculating GCD use the Euclidean Algorithm - Euclid Algorithm in Number theory or use inbuild GCD
(__gcd(N,M))function.
Complexity:
- Time Complexity: Computing the
GCDtakesO(log(min(N,M))). - Space Complexity:
O(1)No extra space required.