Given a floor of size MxN size and tiles of size 2×1, the task is to find the maximum number of tiles required to cover the floor as much as possible of size MxN size.
Note: A tile can either be placed horizontally or vertically and no two tiles should overlap.
Examples:
Input: M = 2, N = 4
Output: 4
Explanation:
4 tiles are needed to cover the floor.Input: M = 3, N = 3
Output: 4
Explanation:
4 tiles are needed to cover the floor.
Approach:
- If N is even, then the task is to place m rows of (N/2) number of tiles to cover the whole floor.
- Else if N is odd, then cover M rows till N – 1 (even) columns in the same way as discussed in the above point and put (M/2) number of tiles in the last column. If both M and N are odd, then one cell of the floor remains uncovered.
- Therefore, the maximum number of tiles is floor((M * N) / 2).
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum number// of tiles required to cover the floor// of size m x n using 2 x 1 size tilesvoid maximumTiles(int n, int m){ // Print the answer cout << (m * n) / 2 << endl;}// Driver Codeint main(){ // Given M and N int M = 3; int N = 4; // Function Call maximumTiles(N, M); return 0;} |
Java
// Java program for the above approach import java.util.*;class GFG{// Function to find the maximum number// of tiles required to cover the floor// of size m x n using 2 x 1 size tilesstatic void maximumTiles(int n, int m){ // Print the answer System.out.println((m * n) / 2);}// Driver codepublic static void main (String[] args){ // Given M and N int M = 3; int N = 4; // Function call maximumTiles(N, M);}}// This code is contributed by offbeat |
Python3
# Python3 program for the above approach # Function to find the maximum number# of tiles required to cover the floor# of size m x n using 2 x 1 size tilesdef maximumTiles(n, m): # Print the answer print(int((m * n) / 2));# Driver codeif __name__ == '__main__': # Given M and N M = 3; N = 4; # Function call maximumTiles(N, M);# This code is contributed by sapnasingh4991 |
C#
// C# program for the above approach using System;class GFG{// Function to find the maximum number// of tiles required to cover the floor// of size m x n using 2 x 1 size tilesstatic void maximumTiles(int n, int m){ // Print the answer Console.WriteLine((m * n) / 2);}// Driver codepublic static void Main(String[] args){ // Given M and N int M = 3; int N = 4; // Function call maximumTiles(N, M);}}// This code is contributed by amal kumar choubey |
Javascript
<script>// JavaScript program for the above approach// Function to find the maximum number// of tiles required to cover the floor// of size m x n using 2 x 1 size tilesfunction maximumTiles(n, m){ // Print the answer document.write((m * n) / 2);} // Driver Code // Given M and N let M = 3; let N = 4; // Function call maximumTiles(N, M); </script> |
Output:
6
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!