Find the number of rectangles of size 2*1 which can be placed inside a rectangle of size n*m
Given two integers n, m. Find the number of rectangles of size 2*1 that can be placed inside a rectangle of size n*m.
Note:
- No two small rectangles overlap.
- Each small rectangle lies entirely inside the large rectangle. It is allowed to touch the edges of the large rectangle.
Examples:
Input : n = 3, m =3 Output : 4 Input : n = 2, m = 4 Output : 4
Approach:
- If N is even, then place M rows of N/2 small rectangles and cover the whole large rectangle.
- If M is even, then place N rows of M/2 small rectangles and cover the whole large rectangle.
- If both are odd then cover N – 1 row of the board with small rectangles and put floor(M/2) small rectangles to the last row. In the worst case (N and M are odd) one cell remains uncovered.
Below is the implementation of the above approach:
C++
// CPP program to Find the number of // rectangles of size 2*1 can be placed // inside a rectangle of size n*m #include <bits/stdc++.h> using namespace std; // function to Find the number of // rectangles of size 2*1 can be placed // inside a rectangle of size n*m int NumberOfRectangles( int n, int m) { // if n is even if (n % 2 == 0) return (n / 2) * m; // if m is even else if (m % 2 == 0) return (m / 2) * n; // if both are odd return (n * m - 1) / 2; } // Driver code int main() { int n = 3, m = 3; // function call cout << NumberOfRectangles(n, m); return 0; } |
C
// C program to Find the number of // rectangles of size 2*1 can be placed // inside a rectangle of size n*m #include <stdio.h> // function to Find the number of // rectangles of size 2*1 can be placed // inside a rectangle of size n*m int NumberOfRectangles( int n, int m) { // if n is even if (n % 2 == 0) return (n / 2) * m; // if m is even else if (m % 2 == 0) return (m / 2) * n; // if both are odd return (n * m - 1) / 2; } // Driver code int main() { int n = 3, m = 3; // function call printf ( "%d" ,NumberOfRectangles(n, m)); return 0; } // This code is contributed by kothavvsaakash. |
Java
// Java program to Find the number of // rectangles of size 2*1 can be placed // inside a rectangle of size n*m public class GFG { // function to Find the number of // rectangles of size 2*1 can be placed // inside a rectangle of size n*m static int NumberOfRectangles( int n, int m) { // if n is even if (n % 2 == 0 ) return (n / 2 ) * m; // if m is even else if (m % 2 == 0 ) return (m / 2 ) * n; // if both are odd return (n * m - 1 ) / 2 ; } public static void main(String args[]) { int n = 3 , m = 3 ; // function call System.out.println(NumberOfRectangles(n, m)); } // This Code is contributed by ANKITRAI1 } |
Python3
# Python 3 program to Find the # number of rectangles of size # 2*1 can be placed inside a # rectangle of size n*m # function to Find the number # of rectangles of size 2*1 # can be placed inside a # rectangle of size n*m def NumberOfRectangles(n, m): # if n is even if (n % 2 = = 0 ): return (n / 2 ) * m # if m is even elif (m % 2 = = 0 ): return (m / / 2 ) * n # if both are odd return (n * m - 1 ) / / 2 # Driver code if __name__ = = "__main__" : n = 3 m = 3 # function call print (NumberOfRectangles(n, m)) # This code is contributed # by ChitraNayal |
C#
// C# program to Find the number of // rectangles of size 2*1 can be placed // inside a rectangle of size n*m using System; class GFG { // function to Find the number of // rectangles of size 2*1 can be placed // inside a rectangle of size n*m static int NumberOfRectangles( int n, int m) { // if n is even if (n % 2 == 0) return (n / 2) * m; // if m is even else if (m % 2 == 0) return (m / 2) * n; // if both are odd return (n * m - 1) / 2; } // Driver Code public static void Main() { int n = 3, m = 3; // function call Console.WriteLine(NumberOfRectangles(n, m)); } // This code is contributed // by Akanksha Rai(Abby_akku) } |
PHP
<?php // PHP program to Find the number of // rectangles of size 2*1 can be placed // inside a rectangle of size n*m // function to Find the number of // rectangles of size 2*1 can be placed // inside a rectangle of size n*m function NumberOfRectangles( $n , $m ) { // if n is even if ( $n % 2 == 0) return ( $n / 2) * $m ; // if m is even else if ( $m % 2 == 0) return ( $m / 2) * $n ; // if both are odd return ( $n * $m - 1) / 2; } // Driver code $n = 3; $m = 3; // function call echo NumberOfRectangles( $n , $m ); // This code is contributed // by Shivi_Aggarwal ?> |
Javascript
<script> // Javascript program to Find the number of // rectangles of size 2*1 can be placed // inside a rectangle of size n*m // Function to Find the number of // rectangles of size 2*1 can be placed // inside a rectangle of size n*m function NumberOfRectangles(n, m) { // If n is even if (n % 2 == 0) return (n / 2) * m; // If m is even else if (m % 2 == 0) return (m / 2) * n; // If both are odd return (n * m - 1) / 2; } // Driver Code var n = 3, m = 3; // Function call document.write(NumberOfRectangles(n, m)); // This code is contributed by Ankita saini </script> |
Output
4
Time Complexity: O(1)
Auxiliary Space: O(1)