Count tiles of dimensions 2 * 1 that can be placed in an M * N rectangular board that satisfies the given conditions

0 0 3 minutes read

Given two integers M and N, the task is to find the minimum number of tiles of size 2 * 1 that can be placed on an M * N grid such that the following conditions are satisfied:

Each tile must completely cover 2 squares of the board.
No pair of tiles may overlap.
Each tile lies must be placed entirely inside the board. It is allowed to touch the edges of the board.

If it is not possible to cover the entire board, print -1

Input: N = 2, M = 4
Output: 4
Explanation: 4 tiles of dimension 2 * 1. Place each tile in one column.

Input: N = 3, M = 3
Output: -1

Approach: Follow the steps below to solve the problem

If N is even, (N / 2) * M tiles can be placed to cover the entire board.
If N is odd, tiles of 2 * 1 tiles, since the length is odd which can not be expressed as a multiple of 2

Below is the implementation of the above approach:

C++

// C++ Program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count tiles of dimensions
// 2 x 1 that can be placed in a grid of
// dimensions M * N as per given conditions
int numberOfTiles(int N, int M)
{
    if (N % 2 == 1) {
        return -1;
    }
 
    // Number of tiles required
    return (N * 1LL * M) / 2;
}
 
// Driver Code
int main()
{
    int N = 2, M = 4;
    cout << numberOfTiles(N, M);
 
    return 0;
}

Java

// Java Program to implement
// the above approach
 
import java.io.*;
 
class GFG {
 
    // Function to count tiles of dimensions
    // 2 x 1 that can be placed in a grid of
    // dimensions M * N as per given conditions
    static int numberOfTiles(int n, int m)
    {
        if (n % 2 == 1) {
            return -1;
        }
        // Number of tiles required
        return (m * n) / 2;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int n = 2, m = 4;
        System.out.println(
            numberOfTiles(n, m));
    }
}

Python

# Python Program to implement
# the above approach
 
# Function to count tiles of dimensions
# 2 x 1 that can be placed in a grid of
# dimensions M * N as per given conditions
def numberOfTiles(N, M):
    if (N % 2 == 1):
        return -1
     
    # Number of tiles required
    return (N * M) // 2
 
# Driver Code
N = 2
M = 4
print(numberOfTiles(N, M))
 
# This code is contributed by shubhamsingh10

C#

// C# Program to implement
// the above approach
 
using System;
 
public class GFG {
 
    // Function to tiles of size 2 x 1
    // find the number of tiles that can
    // be placed as per the given conditions
    static int numberOfTiles(int n, int m)
    {
        if (n % 2 == 1) {
            return -1;
        }
        // Number of tiles required
        return (m * n) / 2;
    }
 
    // Driver Code
    static public void Main()
    {
        int n = 2, m = 4;
        Console.WriteLine(
            numberOfTiles(n, m));
    }
}

Javascript

<script>
 
// Javascript Program to implement
// the above approach
 
// Function to count tiles of dimensions
// 2 x 1 that can be placed in a grid of
// dimensions M * N as per given conditions
function numberOfTiles(n, m)
{
    if (n % 2 == 1) 
    {
        return -1;
    }
     
    // Number of tiles required
    return (m * n) / 2;
}
 
// Driver Code
var n = 2, m = 4;
 
document.write(numberOfTiles(n, m));
 
// This code is contributed by kirti
 
</script>

Output:

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 zambiatek!