write a python program for Given an area of N X M. You have infinite number of tiles of size 2i X 2i, where i = 0, 1, 2,... so
on. The task is to find minimum number of tiles required to fill the given area with tiles.
Input: N = 5, M = 6.
Output: 9
Area of 5 X 6 can be covered with minimum 9 tiles.
6 tiles of 1 X 1,2 tiles of 2 X 2, 1 tile of 4 X 4.
4X4
Input : N = 10, M = 5.
Output : 14
Answers
Answer:
The idea is to divide the given area into the nearest 2i X 2i.
Let’s divide the problem into cases:
Case 1: if N is odd and M is even, fill the row or column with M number of 1 X 1 tiles. Then count the minimum number of tiles for N/2 X M/2 size of the area. Similarly, if M is odd and N is even, add N to our answer and find a minimum number of tiles for the N/2 X M/2 area.
Case 2: If N and M both are odd, fill one row and one column, so add N + M – 1 to the answer and find the minimum number of tiles required to fill the N/2 X M/2 area.
Case 3: If N and M both are even, calculate the minimum number of tiles required to fill the area with N/2 X M/2 area. Because halving both the dimensions doesn’t change the number of tiles required.
Below is the implementation of this approach:
Explanation:
def minTiles(n, m):
# base case, when area is 0.
if n == 0 or m == 0:
return 0
# If n and m both are even, calculate
# tiles for n/2 x m/2
# Halfing both dimensions doesn't
# change the number of tiles
elif n%2 == 0 and m%2 == 0:
return minTiles(int(n/2), int(m/2))
# If n is even and m is odd
# Use a row of 1x1 tiles
elif n % 2 == 0 and m % 2 == 1:
return (n + minTiles(int(n/2), int(m/2)))
# If n is odd and m is even
# Use a column of 1x1 tiles
elif n % 2 == 1 and m % 2 == 0:
return (m + minTiles(int(n/2), int(m/2)))
# If n and m are odd add
# row + column number of tiles
else:
return (n + m - 1 + minTiles(int(n/2), int(m/2)))
# Driven Program
n = 5
m = 6
print (minTiles(n, m))