Google Interview Question — LeetCode 1240

In this post, we are going to discuss leetcode 1240 — Tiling a Rectangle with the Fewest Squares, which is asked in Google interviews.

Problem Analysis

Given a rectangle of size n x m, return the minimum number of integer-sided squares that tile the rectangle.

Example 1:

Input: n = 2, m = 3 
Output: 3 
Explanation: 3 squares are necessary to cover the rectangle. 2 (squares of 1x1) 1 (square of 2x2)

Example 2:

Input: n = 5, m = 8 
Output: 5

Example 3:

Input: n = 11, m = 13 
Output: 6

My Thinking Process

This looks like a very difficult problem, and seems like no idea to start with. But if you have been following my posts, you will find this problem is very straight forward!

Focus eon the keyword in the question statement: “ minimum number of squares” to fill the rectangle. As I have mentioned multiple times, whenever we see the keyword to that to reach a target state with minimum number of steps, it is a BFS problem!