Given three numbers N,M ,a . Find Number of squares of dimension a*a required to cover N*M rectangle.
Note:
- It’s allowed to cover the surface larger than the rectangle, but the rectangle has to be covered.
- It’s not allowed to break a square.
- The sides of squares should be parallel to the sides of the rectangle.
Input: N = 6, M = 6, a = 4
Output: 4
Input: N = 2, M = 3, a = 1
Output: 6
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
Approach: An efficient approach is to make an observation and find a formula. The constraint that edges of each square must be parallel to the edges of the rectangle allows to analyze X and Y axes separately, that is, how many squares of length ‘a’ are needed to cover squares of length ‘m’ and ‘n’ and take the product of these two quantities. The number of small squares of side length ‘a’ required to cover ‘m’ sized square are ceil(m/a). Similarly, number of ‘a’ sized squares required to cover ‘n’ sized square are ceil(n/a).
So, the answer will be ceil(m/a)*ceil(n/a).
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int Squares( int n, int m, int a)
{
return ((m + a - 1) / a) * ((n + a - 1) / a);
}
int main()
{
int n = 6, m = 6, a = 4;
cout << Squares(n, m, a);
return 0;
}
|
C
#include <stdio.h>
int Squares( int n, int m, int a)
{
return ((m + a - 1) / a) * ((n + a - 1) / a);
}
int main()
{
int n = 6, m = 6, a = 4;
printf ( "%d" ,Squares(n, m, a));
return 0;
}
|
Java
import java.util.*;
class solution
{
static int Squares( int n, int m, int a)
{
return ((m + a - 1 ) / a) * ((n + a - 1 ) / a);
}
public static void main(String arr[])
{
int n = 6 , m = 6 , a = 4 ;
System.out.println(Squares(n, m, a));
}
}
|
Python 3
def Squares(n, m, a):
return (((m + a - 1 ) / / a) *
((n + a - 1 ) / / a))
if __name__ = = "__main__" :
n = 6
m = 6
a = 4
print (Squares(n, m, a))
|
C#
using System;
class GFG
{
static int Squares( int n, int m, int a)
{
return ((m + a - 1) / a) * ((n + a - 1) / a);
}
static void Main()
{
int n = 6, m = 6, a = 4;
Console.WriteLine(Squares(n, m, a));
}
}
|
Javascript
<script>
function Squares(n, m, a)
{
return parseInt(((m + a - 1) / a)) *
parseInt(((n + a - 1) / a));
}
var n = 6, m = 6, a = 4;
document.write(Squares(n, m, a));
</script>
|
PHP
<?php
function Squares( $n , $m , $a )
{
return ((int)(( $m + $a - 1) / $a )) *
((int)(( $n + $a - 1) / $a ));
}
$n = 6; $m = 6; $a = 4;
echo Squares( $n , $m , $a );
?>
|
Time Complexity: O(1), since there is no loop or recursion.
Auxiliary Space: O(1), since no extra space has been taken.
Approach#2: Using math
The approach of this algorithm is to calculate the number of squares required to cover the rows and columns of the given N x M rectangle. Then, the product of the number of squares required for rows and columns is returned as the output.
Algorithm
1. Calculate the number of squares required to cover the rows of the rectangle using the ceil function from the math library, i.e., rows = math.ceil(N / a).
2. Calculate the number of squares required to cover the columns of the rectangle using the ceil function from the math library, i.e., cols = math.ceil(M / a).
3. Return the product of the number of squares required for rows and columns, i.e., rows * cols.
C++
#include <iostream>
#include <cmath> // For using ceil function
using namespace std;
int num_squares2( int N, int M, int a) {
int rows = ceil ( static_cast < double >(N) / a);
int cols = ceil ( static_cast < double >(M) / a);
return rows * cols;
}
int main() {
int N = 2;
int M = 3;
int a = 1;
cout << num_squares2(N, M, a) << endl;
return 0;
}
|
Java
import java.lang.Math;
public class GFG {
public static int num_squares2( int N, int M, int a) {
int rows = ( int ) Math.ceil(( double ) N / a);
int cols = ( int ) Math.ceil(( double ) M / a);
return rows * cols;
}
public static void main(String[] args) {
int N = 2 ;
int M = 3 ;
int a = 1 ;
System.out.println(num_squares2(N, M, a));
}
}
|
Python3
import math
def num_squares2(N, M, a):
rows = math.ceil(N / a)
cols = math.ceil(M / a)
return rows * cols
N = 2
M = 3
a = 1
print (num_squares2(N, M, a))
|
C#
using System;
public class GFG
{
public static int NumSquares2( int N, int M, int a)
{
int rows = ( int )Math.Ceiling(( double )N / a);
int cols = ( int )Math.Ceiling(( double )M / a);
return rows * cols;
}
public static void Main( string [] args)
{
int N = 2;
int M = 3;
int a = 1;
Console.WriteLine(NumSquares2(N, M, a));
}
}
|
Javascript
const num_squares2 = (N, M, a) => {
const rows = Math.ceil(N / a);
const cols = Math.ceil(M / a);
return rows * cols;
}
const N = 2;
const M = 3;
const a = 1;
console.log(num_squares2(N, M, a));
|
Time complexity: O(1), which means it is constant time complexity. This is because the algorithm performs a fixed number of operations, which are independent of the input size.
Space complexity: O(1), which means it uses a constant amount of space. This is because it only stores a fixed number of variables, which are independent of the input size.