Azulejos mínimos de tamaños en potencias de dos para cubrir toda el área

Dada un área de NXM . Tienes el número infinito de fichas de tamaño 2 ⁱ X 2 ⁱ , donde i = 0, 1, 2,… y así sucesivamente. La tarea es encontrar el número mínimo de mosaicos necesarios para llenar el área dada con mosaicos.
Ejemplos: 
 

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

La idea es dividir el área dada en el 2 ⁱ X 2 ⁱ más cercano . 
Dividamos el problema en casos: 
Caso 1: si N es impar y M es par, llena la fila o columna con M número de fichas 1 X 1. Luego cuente el número mínimo de mosaicos para el tamaño N/2 XM/2 del área. De manera similar, si M es impar y N es par, agregue N a nuestra respuesta y encuentre un número mínimo de mosaicos para el área N/2 XM/2.
Caso 2: si N y M son impares, complete una fila y una columna, de modo que sume N + M – 1 a la respuesta y encuentre la cantidad mínima de mosaicos necesarios para llenar el área N/2 XM/2.
Caso 3:Si N y M son pares, calcule el número mínimo de mosaicos necesarios para llenar el área con N/2 XM/2 área. Porque reducir a la mitad ambas dimensiones no cambia la cantidad de mosaicos requeridos.
A continuación se muestra la implementación de este enfoque: 
 

#include<bits/stdc++.h>
using namespace std;
 
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));
}
 
// Driven Program
int main()
{
  int n = 5, m = 6;
 
  cout << minTiles(n, m) << endl;
  return 0;
}

// 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.

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# code for Minimum tiles of
// sizes in powers of two to cover
// whole area
using System;
 
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()
    {
        int n = 5, m = 6;
         
        Console.WriteLine(minTiles(n, m));
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP program 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 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
    else if ($n % 2 == 0 and
                $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 and $m % 2 == 1)
        return floor($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 and
             $m % 2 == 0)
        return ($m + minTiles($n / 2,
                              $m / 2));
     
    // If n and m are odd
    // add row + column number of tiles
    else
        return floor($n + $m - 1 +
                    minTiles($n / 2, $m / 2));
}
 
// Driver Code
$n = 5; $m = 6;
echo minTiles($n, $m);
 
// This code is contributed by anuj_67.
?>

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

Producción:  

9

Análisis de Complejidad:

Complejidad de tiempo: O(log(min(n,m))/log(2)), donde n y m son dimensiones de mosaicos. 

Espacio auxiliar: O(log(min(n,m))/log(2)), porque estamos agregando un elemento a la pila durante cada llamada de recurrencia.

Este artículo es una contribución de Anuj Chauhan (anuj0503) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.