Tiling A Rectangle With The Fewest Squares - Leetcode Solution

Problem: Given a rectangle of size n x m, find the minimum number of squares that can be used to tile the rectangle.

Solution:

Approach 1: Brute Force

The brute force approach is to generate all possible combinations of squares, starting from the largest square that can fit inside the rectangle. We can calculate the number of squares required for each combination and choose the combination with the least number of squares.

Time complexity: O(n²m²).

Approach 2: Dynamic Programming

We can solve the problem using dynamic programming. We create a table of size n+1 x m+1 to store the minimum number of squares required to tile a rectangle of size i x j. The base cases are when i = 1 or j = 1, where we need at least min(i, j) squares. We then fill up the table using the recurrence relation:

dp[i][j] = min(dp[i-k][j] + dp[k][j-k], dp[i][j-k] + dp[i-k][k])

Here, k varies from 1 to i/2 or j/2. The first term in the minimum represents tiling the rectangle vertically and the second term represents tiling the rectangle horizontally.

The final answer is stored in dp[n][m].

Time complexity: O(n²m²).

Approach 3: Mathematical Solution

We can also solve the problem mathematically using the following formula:

solution = m * n - gcd(m, n) * (1 + ((m/gcd(m,n))- 1) + ((n/gcd(m,n)) - 1))

Here, gcd(m, n) represents the greatest common divisor of m and n.

Time complexity: O(log(min(m, n))).

Code:

Approach 2: Dynamic Programming

public int tilingRectangle(int n, int m) { int[][] dp = new int[n+1][m+1];

// Base Cases
for(int i = 1; i <= n; i++)
    dp[i][1] = i;

for(int j = 1; j <= m; j++)
    dp[1][j] = j;

// Filling up the table
for(int i = 2; i <= n; i++) {
    for(int j = 2; j <= m; j++) {
        dp[i][j] = Integer.MAX_VALUE;
        for(int k = 1; k <= i/2; k++) 
            dp[i][j] = Math.min(dp[i][j], dp[i-k][j] + dp[k][j-k]);
        
        for(int k = 1; k <= j/2; k++) 
            dp[i][j] = Math.min(dp[i][j], dp[i][j-k] + dp[i-k][k]);
    }
}

return dp[n][m];

}

Approach 3: Mathematical Solution

public int tilingRectangle(int n, int m) { int gcd = gcd(n, m); return n * m / (gcd * gcd) - (n / gcd) * (m / gcd); }

private int gcd(int a, int b) { if(b == 0) return a; return gcd(b, a % b); }

1