Minimum tiles of sizes in powers of two to cover whole area
Given an area of N X M. You have the infinite number of tiles of size 2i X 2i, where i = 0, 1, 2,… so on. The task is to find the minimum number of tiles required to fill the given area with tiles.
Examples:
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.
Input : N = 10, M = 5. Output : 14
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:
C++
< div id= "highlighter_190951" class = "syntaxhighlighter nogutter " ><table border= "0" cellpadding= "0" cellspacing= "0" ><tbody><tr><td class = "code" >< div class = "container" >< div class = "line number1 index0 alt2" ><code class = "preprocessor" >#include<bits/stdc++.h></code></ div >< div class = "line number2 index1 alt1" ><code class = "keyword bold" > using </code> <code class = "keyword bold" > namespace </code> <code class = "plain" >std;</code></ div >< div class = "line number3 index2 alt2" > </ div >< div class = "line number4 index3 alt1" ><code class = "color1 bold" > int </code> <code class = "plain" >minTiles(</code><code class = "color1 bold" > int </code> <code class = "plain" >n, </code><code class = "color1 bold" > int </code> <code class = "plain" >m)</code></ div >< div class = "line number5 index4 alt2" ><code class = "plain" >{</code></ div >< div class = "line number6 index5 alt1" ><code class = "undefined spaces" > </code><code class = "comments" > // base case, when area is 0.</code></div><div class="line number7 index6 alt2"><code class="undefined spaces"> </code><code class="keyword bold">if</code> <code class="plain">(n == 0 || m == 0)</code></div><div class="line number8 index7 alt1"><code class="undefined spaces"> </code><code class="keyword bold">return</code> <code class="plain">0;</code></div><div class="line number9 index8 alt2"> </div><div class="line number10 index9 alt1"><code class="undefined spaces"> </code><code class="comments">// If n and m both are even, calculate tiles for n/2 x m/2</code></div><div class="line number11 index10 alt2"><code class="undefined spaces"> </code><code class="comments">// Halving both dimensions doesn't change the number of tiles</code></div><div class="line number12 index11 alt1"><code class="undefined spaces"> </code><code class="keyword bold">else</code> <code class="keyword bold">if</code> <code class="plain">(n%2 == 0 && m%2 == 0)</code></div><div class="line number13 index12 alt2"><code class="undefined spaces"> </code><code class="keyword bold">return</code> <code class="plain">minTiles(n/2, m/2);</code></div><div class="line number14 index13 alt1"><code class="undefined spaces"> </code> </div><div class="line number15 index14 alt2"><code class="undefined spaces"> </code><code class="comments">// If n is even and m is odd</code></div><div class="line number16 index15 alt1"><code class="undefined spaces"> </code><code class="comments">// Use a row of 1x1 tiles</code></div><div class="line number17 index16 alt2"><code class="undefined spaces"> </code><code class="keyword bold">else</code> <code class="keyword bold">if</code> <code class="plain">(n%2 == 0 && m%2 == 1)</code></div><div class="line number18 index17 alt1"><code class="undefined spaces"> </code><code class="keyword bold">return</code> <code class="plain">(n + minTiles(n/2, m/2));</code></div><div class="line number19 index18 alt2"> </div><div class="line number20 index19 alt1"><code class="undefined spaces"> </code><code class="comments">// If n is odd and m is even</code></div><div class="line number21 index20 alt2"><code class="undefined spaces"> </code><code class="comments">// Use a column of 1x1 tiles</code></div><div class="line number22 index21 alt1"><code class="undefined spaces"> </code><code class="keyword bold">else</code> <code class="keyword bold">if</code> <code class="plain">(n%2 == 1 && m%2 == 0)</code></div><div class="line number23 index22 alt2"><code class="undefined spaces"> </code><code class="keyword bold">return</code> <code class="plain">(m + minTiles(n/2, m/2));</code></div><div class="line number24 index23 alt1"> </div><div class="line number25 index24 alt2"><code class="undefined spaces"> </code><code class="comments">// If n and m are odd</code></div><div class="line number26 index25 alt1"><code class="undefined spaces"> </code><code class="comments">// add row + column number of tiles</code></div><div class="line number27 index26 alt2"><code class="undefined spaces"> </code><code class="keyword bold">else</code></div><div class="line number28 index27 alt1"><code class="undefined spaces"> </code><code class="keyword bold">return</code> <code class="plain">(n + m - 1 + minTiles(n/2, m/2)); </code></div><div class="line number29 index28 alt2"><code class="plain">}</code></div><div class="line number30 index29 alt1"> </div><div class="line number31 index30 alt2"><code class="comments">// Driven Program</code></div><div class="line number32 index31 alt1"><code class="color1 bold">int</code> <code class="plain">main()</code></div><div class="line number33 index32 alt2"><code class="plain">{</code></div><div class="line number34 index33 alt1"><code class="undefined spaces"> </code><code class="color1 bold">int</code> <code class="plain">n = 5, m = 6;</code></div><div class="line number35 index34 alt2"> </div><div class="line number36 index35 alt1"><code class="undefined spaces"> </code><code class="plain">cout << minTiles(n, m) << endl;</code></div><div class="line number37 index36 alt2"><code class="undefined spaces"> </code><code class="keyword bold">return</code> <code class="plain">0;</code></div><div class="line number38 index37 alt1"><code class="plain">}</code></div></div></td></tr></tbody></table></div> |
Java
// Java code for Minimum tiles of // sizes in powers of two to cover // whole area class GFG { static int minTiles( int n, int m) { // base case, when area is 0. if (n == 0 || m == 0 ) return 0 ; // If n and m both are even, // calculate tiles for n/2 x m/2 // Halving both dimensions doesn't // change the number of tiles else if (n % 2 == 0 && m % 2 == 0 ) return minTiles(n / 2 , m / 2 ); // If n is even and m is odd // Use a row of 1x1 tiles else if (n % 2 == 0 && m % 2 == 1 ) return (n + minTiles(n / 2 , m / 2 )); // If n is odd and m is even // Use a column of 1x1 tiles else if (n % 2 == 1 && m % 2 == 0 ) return (m + minTiles(n / 2 , m / 2 )); // If n and m are odd // add row + column number of tiles else return (n + m - 1 + minTiles(n / 2 , m / 2 )); } // Driver code public static void main (String[] args) { int n = 5 , m = 6 ; System.out.println(minTiles(n, m)); } } // This code is contributed by Anant Agarwal. |
Python3
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 # Halving 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)) # This code is contributed # by Shreyanshi Arun. |
C#
<div id= "highlighter_324618" class = "syntaxhighlighter nogutter " ><table border= "0" cellpadding= "0" cellspacing= "0" ><tbody><tr><td class = "code" ><div class = "container" ><div class = "line number1 index0 alt2" ><code class = "comments" > // C# code for Minimum tiles of</code></div><div class="line number2 index1 alt1"><code class="comments">// sizes in powers of two to cover</code></div><div class="line number3 index2 alt2"><code class="comments">// whole area</code></div><div class="line number4 index3 alt1"><code class="keyword">using</code> <code class="plain">System;</code></div><div class="line number5 index4 alt2"> </div><div class="line number6 index5 alt1"><code class="keyword">class</code> <code class="plain">GFG {</code></div><div class="line number7 index6 alt2"> </div><div class="line number8 index7 alt1"><code class="undefined spaces"> </code><code class="keyword">static</code> <code class="keyword">int</code> <code class="plain">minTiles(</code><code class="keyword">int</code> <code class="plain">n, </code><code class="keyword">int</code> <code class="plain">m)</code></div><div class="line number9 index8 alt2"><code class="undefined spaces"> </code><code class="plain">{</code></div><div class="line number10 index9 alt1"><code class="undefined spaces"> </code> </div><div class="line number11 index10 alt2"><code class="undefined spaces"> </code><code class="comments">// base case, when area is 0.</code></div><div class="line number12 index11 alt1"><code class="undefined spaces"> </code><code class="keyword">if</code> <code class="plain">(n == 0 || m == 0)</code></div><div class="line number13 index12 alt2"><code class="undefined spaces"> </code><code class="keyword">return</code> <code class="plain">0;</code></div><div class="line number14 index13 alt1"> </div><div class="line number15 index14 alt2"><code class="undefined spaces"> </code><code class="comments">// If n and m both are even,</code></div><div class="line number16 index15 alt1"><code class="undefined spaces"> </code><code class="comments">// calculate tiles for n/2 x m/2</code></div><div class="line number17 index16 alt2"><code class="undefined spaces"> </code><code class="comments">// Halving both dimensions doesn't</code></div><div class="line number18 index17 alt1"><code class="undefined spaces"> </code><code class="comments">// change the number of tiles</code></div><div class="line number19 index18 alt2"><code class="undefined spaces"> </code><code class="keyword">else</code> <code class="keyword">if</code> <code class="plain">(n % 2 == 0 && m % 2 == 0)</code></div><div class="line number20 index19 alt1"><code class="undefined spaces"> </code><code class="keyword">return</code> <code class="plain">minTiles(n / 2, m / 2);</code></div><div class="line number21 index20 alt2"> </div><div class="line number22 index21 alt1"><code class="undefined spaces"> </code><code class="comments">// If n is even and m is odd</code></div><div class="line number23 index22 alt2"><code class="undefined spaces"> </code><code class="comments">// Use a row of 1x1 tiles</code></div><div class="line number24 index23 alt1"><code class="undefined spaces"> </code><code class="keyword">else</code> <code class="keyword">if</code> <code class="plain">(n % 2 == 0 && m % 2 == 1)</code></div><div class="line number25 index24 alt2"><code class="undefined spaces"> </code><code class="keyword">return</code> <code class="plain">(n + minTiles(n / 2, m / 2));</code></div><div class="line number26 index25 alt1"> </div><div class="line number27 index26 alt2"><code class="undefined spaces"> </code><code class="comments">// If n is odd and m is even</code></div><div class="line number28 index27 alt1"><code class="undefined spaces"> </code><code class="comments">// Use a column of 1x1 tiles</code></div><div class="line number29 index28 alt2"><code class="undefined spaces"> </code><code class="keyword">else</code> <code class="keyword">if</code> <code class="plain">(n % 2 == 1 && m % 2 == 0)</code></div><div class="line number30 index29 alt1"><code class="undefined spaces"> </code><code class="keyword">return</code> <code class="plain">(m + minTiles(n / 2, m / 2));</code></div><div class="line number31 index30 alt2"> </div><div class="line number32 index31 alt1"><code class="undefined spaces"> </code><code class="comments">// If n and m are odd</code></div><div class="line number33 index32 alt2"><code class="undefined spaces"> </code><code class="comments">// add row + column number of tiles</code></div><div class="line number34 index33 alt1"><code class="undefined spaces"> </code><code class="keyword">else</code></div><div class="line number35 index34 alt2"><code class="undefined spaces"> </code><code class="keyword">return</code> <code class="plain">(n + m - 1 + minTiles(n / 2, m / 2));</code></div><div class="line number36 index35 alt1"><code class="undefined spaces"> </code><code class="plain">}</code></div><div class="line number37 index36 alt2"> </div><div class="line number38 index37 alt1"><code class="undefined spaces"> </code><code class="comments">// Driver code</code></div><div class="line number39 index38 alt2"><code class="undefined spaces"> </code><code class="keyword">public</code> <code class="keyword">static</code> <code class="keyword">void</code> <code class="plain">Main()</code></div><div class="line number40 index39 alt1"><code class="undefined spaces"> </code><code class="plain">{</code></div><div class="line number41 index40 alt2"><code class="undefined spaces"> </code><code class="keyword">int</code> <code class="plain">n = 5, m = 6;</code></div><div class="line number42 index41 alt1"><code class="undefined spaces"> </code> </div><div class="line number43 index42 alt2"><code class="undefined spaces"> </code><code class="plain">Console.WriteLine(minTiles(n, m));</code></div><div class="line number44 index43 alt1"><code class="undefined spaces"> </code><code class="plain">}</code></div><div class="line number45 index44 alt2"><code class="plain">}</code></div><div class="line number46 index45 alt1"> </div><div class="line number47 index46 alt2"><code class="comments">// This code is contributed by vt_m.</code></div></div></td></tr></tbody></table></div> |
PHP
<div id= "highlighter_613659" class = "syntaxhighlighter nogutter " ><table border= "0" cellpadding= "0" cellspacing= "0" ><tbody><tr><td class = "code" ><div class = "container" ><div class = "line number1 index0 alt2" ><code class = "plain" ><?php</code></div><div class = "line number2 index1 alt1" ><code class = "comments" > // PHP program for Minimum tiles of </code></div><div class="line number3 index2 alt2"><code class="comments">// sizes in powers of two to cover</code></div><div class="line number4 index3 alt1"><code class="comments">// whole area</code></div><div class="line number5 index4 alt2"> </div><div class="line number6 index5 alt1"><code class="keyword">function</code> <code class="plain">minTiles(</code><code class="variable">$n</code><code class="plain">, </code><code class="variable">$m</code><code class="plain">)</code></div><div class="line number7 index6 alt2"><code class="plain">{</code></div><div class="line number8 index7 alt1"><code class="undefined spaces"> </code> </div><div class="line number9 index8 alt2"><code class="undefined spaces"> </code><code class="comments">// base case, when area is 0.</code></div><div class="line number10 index9 alt1"><code class="undefined spaces"> </code><code class="keyword">if</code> <code class="plain">(</code><code class="variable">$n</code> <code class="plain">== 0 </code><code class="keyword">or</code> <code class="variable">$m</code> <code class="plain">== 0)</code></div><div class="line number11 index10 alt2"><code class="undefined spaces"> </code><code class="keyword">return</code> <code class="plain">0;</code></div><div class="line number12 index11 alt1"><code class="undefined spaces"> </code> </div><div class="line number13 index12 alt2"><code class="undefined spaces"> </code><code class="comments">// If n and m both are even,</code></div><div class="line number14 index13 alt1"><code class="undefined spaces"> </code><code class="comments">// calculate tiles for n/2 x m/2</code></div><div class="line number15 index14 alt2"><code class="undefined spaces"> </code><code class="comments">// Halving both dimensions doesn't </code></div><div class="line number16 index15 alt1"><code class="undefined spaces"> </code><code class="comments">// change the number of tiles</code></div><div class="line number17 index16 alt2"><code class="undefined spaces"> </code><code class="keyword">else</code> <code class="keyword">if</code> <code class="plain">(</code><code class="variable">$n</code> <code class="plain">% 2 == 0 </code><code class="keyword">and</code></div><div class="line number18 index17 alt1"><code class="undefined spaces"> </code><code class="variable">$m</code> <code class="plain">% 2 == 0)</code></div><div class="line number19 index18 alt2"><code class="undefined spaces"> </code><code class="keyword">return</code> <code class="plain">minTiles(</code><code class="variable">$n</code> <code class="plain">/ 2, </code><code class="variable">$m</code> <code class="plain">/ 2);</code></div><div class="line number20 index19 alt1"><code class="undefined spaces"> </code> </div><div class="line number21 index20 alt2"><code class="undefined spaces"> </code><code class="comments">// If n is even and m is odd</code></div><div class="line number22 index21 alt1"><code class="undefined spaces"> </code><code class="comments">// Use a row of 1x1 tiles</code></div><div class="line number23 index22 alt2"><code class="undefined spaces"> </code><code class="keyword">else</code> <code class="keyword">if</code> <code class="plain">(</code><code class="variable">$n</code> <code class="plain">% 2 == 0 </code><code class="keyword">and</code> <code class="variable">$m</code> <code class="plain">% 2 == 1)</code></div><div class="line number24 index23 alt1"><code class="undefined spaces"> </code><code class="keyword">return</code> <code class="functions">floor</code><code class="plain">(</code><code class="variable">$n</code> <code class="plain">+ minTiles(</code><code class="variable">$n</code> <code class="plain">/ 2,</code></div><div class="line number25 index24 alt2"><code class="undefined spaces"> </code><code class="variable">$m</code> <code class="plain">/ 2));</code></div><div class="line number26 index25 alt1"><code class="undefined spaces"> </code> </div><div class="line number27 index26 alt2"><code class="undefined spaces"> </code><code class="comments">// If n is odd and m is even</code></div><div class="line number28 index27 alt1"><code class="undefined spaces"> </code><code class="comments">// Use a column of 1x1 tiles</code></div><div class="line number29 index28 alt2"><code class="undefined spaces"> </code><code class="keyword">else</code> <code class="keyword">if</code> <code class="plain">(</code><code class="variable">$n</code> <code class="plain">% 2 == 1 </code><code class="keyword">and</code></div><div class="line number30 index29 alt1"><code class="undefined spaces"> </code><code class="variable">$m</code> <code class="plain">% 2 == 0)</code></div><div class="line number31 index30 alt2"><code class="undefined spaces"> </code><code class="keyword">return</code> <code class="plain">(</code><code class="variable">$m</code> <code class="plain">+ minTiles(</code><code class="variable">$n</code> <code class="plain">/ 2, </code></div><div class="line number32 index31 alt1"><code class="undefined spaces"> </code><code class="variable">$m</code> <code class="plain">/ 2));</code></div><div class="line number33 index32 alt2"><code class="undefined spaces"> </code> </div><div class="line number34 index33 alt1"><code class="undefined spaces"> </code><code class="comments">// If n and m are odd</code></div><div class="line number35 index34 alt2"><code class="undefined spaces"> </code><code class="comments">// add row + column number of tiles</code></div><div class="line number36 index35 alt1"><code class="undefined spaces"> </code><code class="keyword">else</code></div><div class="line number37 index36 alt2"><code class="undefined spaces"> </code><code class="keyword">return</code> <code class="functions">floor</code><code class="plain">(</code><code class="variable">$n</code> <code class="plain">+ </code><code class="variable">$m</code> <code class="plain">- 1 + </code></div><div class="line number38 index37 alt1"><code class="undefined spaces"> </code><code class="plain">minTiles(</code><code class="variable">$n</code> <code class="plain">/ 2, </code><code class="variable">$m</code> <code class="plain">/ 2)); </code></div><div class="line number39 index38 alt2"><code class="plain">}</code></div><div class="line number40 index39 alt1"> </div><div class="line number41 index40 alt2"><code class="comments">// Driver Code</code></div><div class="line number42 index41 alt1"><code class="variable">$n</code> <code class="plain">= 5; </code><code class="variable">$m</code> <code class="plain">= 6;</code></div><div class="line number43 index42 alt2"><code class="functions">echo</code> <code class="plain">minTiles(</code><code class="variable">$n</code><code class="plain">, </code><code class="variable">$m</code><code class="plain">);</code></div><div class="line number44 index43 alt1"> </div><div class="line number45 index44 alt2"><code class="comments">// This code is contributed by anuj_67.</code></div><div class="line number46 index45 alt1"><code class="plain">?></code></div></div></td></tr></tbody></table></div> |
Javascript
<script> // JavaScript code for Minimum tiles of // sizes in powers of two to cover // whole area function minTiles(n, m) { // base case, when area is 0. if (n == 0 || m == 0) return 0; // If n and m both are even, // calculate tiles for n/2 x m/2 // Halving both dimensions doesn't // change the number of tiles else if (n % 2 == 0 && m % 2 == 0) return minTiles((n / 2),(m / 2)); // If n is even and m is odd // Use a row of 1x1 tiles else if (n % 2 == 0 && m % 2 == 1) return (n + minTiles(Math.floor(n / 2), Math.floor(m / 2))); // If n is odd and m is even // Use a column of 1x1 tiles else if (n % 2 == 1 && m % 2 == 0) return (m + minTiles(Math.floor(n / 2), Math.floor(m / 2))); // If n and m are odd // add row + column number of tiles else return (n + m - 1 + minTiles(Math.floor(n / 2), Math.floor(m / 2))); } // Driver Code let n = 5, m = 6; document.write(Math.floor(minTiles(n, m))); </script> |
Output:
9
Complexity Analysis:
Time Complexity: O(log(min(n,m))/log(2)), where n and m are dimensions of tiles.
Auxiliary Space: O(log(min(n,m))/log(2)), because we are adding an element to the stack during each recursion call.