Corte de papel en un número mínimo de cuadrados

Dado un papel de tamaño A x B. La tarea es cortar el papel en cuadrados de cualquier tamaño. Encuentra el número mínimo de cuadrados que se pueden cortar del papel. 
Ejemplos: 
 

Input  : 13 x 29
Output : 9
Explanation : 
2 (squares of size 13x13) + 
4 (squares of size 3x3) + 
3 (squares of size 1x1)=9

Input  : 4 x 5
Output : 5
Explanation : 
1 (squares of size 4x4) + 
4 (squares of size 1x1)

Sabemos que si queremos cortar un número mínimo de cuadrados del papel, primero tendríamos que cortar el cuadrado más grande posible del papel y el cuadrado más grande tendrá el mismo lado que el lado más pequeño del papel. Por ejemplo, si el papel tiene un tamaño de 13 x 29, entonces el cuadrado máximo será de lado 13, por lo que podemos cortar 2 cuadrados de tamaño 13 x 13 (29/13 = 2). Ahora el papel restante tendrá un tamaño de 3 x 13. Del mismo modo, podemos cortar el papel restante utilizando 4 cuadrados de tamaño 3 x 3 y 3 cuadrados de 1 x 1. Por lo tanto, se pueden cortar un mínimo de 9 cuadrados del papel de tamaño 13 x29
 

A continuación se muestra la implementación del enfoque anterior. 
 

// C++ program to find minimum number of squares
// to cut a paper.
#include<bits/stdc++.h>
using namespace std;
 
// Returns min number of squares needed
int minimumSquare(int a, int b)
{
    long long result = 0, rem = 0;
 
    // swap if a is small size side .
    if (a < b)
        swap(a, b);
 
    // Iterate until small size side is
    // greater then 0
    while (b > 0)
    {
        // Update result
        result += a/b;
 
        long long rem = a % b;
        a = b;
        b = rem;
    }
 
    return result;
}
 
// Driver code
int main()
{
    int n = 13, m = 29;
    cout << minimumSquare(n, m);
    return 0;
}

// Java program to find minimum
// number of squares to cut a paper.
class GFG{
     
// To swap two numbers
static void swap(int a,int b)
{
    int temp = a;
    a = b;
    b = temp;
}
 
// Returns min number of squares needed
static int minimumSquare(int a, int b)
{
    int result = 0, rem = 0;
 
    // swap if a is small size side .
    if (a < b)
        swap(a, b);
 
    // Iterate until small size side is
    // greater then 0
    while (b > 0)
    {
        // Update result
        result += a/b;
        rem = a % b;
        a = b;
        b = rem;
    }
 
    return result;
}
 
// Driver code
public static void main(String[] args)
{
    int n = 13, m = 29;
    System.out.println(minimumSquare(n, m));
}
}
 
//This code is contributed by Smitha Dinesh Semwal.

# Python 3 program to find minimum
# number of squares to cut a paper.
 
# Returns min number of squares needed
def minimumSquare(a, b):
 
    result = 0
    rem = 0
 
    # swap if a is small size side .
    if (a < b):
        a, b = b, a
 
    # Iterate until small size side is
    # greater then 0
    while (b > 0):
     
        # Update result
        result += int(a / b)
 
        rem = int(a % b)
        a = b
        b = rem
 
    return result
 
# Driver code
n = 13
m = 29
 
print(minimumSquare(n, m))
 
# This code is contributed by
# Smitha Dinesh Semwal

// C# program to find minimum
// number of squares to cut a paper.
using System;
     
class GFG
{
     
// To swap two numbers
static void swap(int a, int b)
{
    int temp = a;
    a = b;
    b = temp;
}
 
// Returns min number of squares needed
static int minimumSquare(int a, int b)
{
    int result = 0, rem = 0;
 
    // swap if a is small size side .
    if (a < b)
        swap(a, b);
 
    // Iterate until small size side is
    // greater then 0
    while (b > 0)
    {
        // Update result
        result += a / b;
        rem = a % b;
        a = b;
        b = rem;
    }
    return result;
}
 
// Driver code
public static void Main(String[] args)
{
    int n = 13, m = 29;
    Console.WriteLine(minimumSquare(n, m));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript program to find
// minimum number of squares
// to cut a paper.
 
// Returns min number of squares needed
function minimumSquare(a, b)
{
    let result = 0, rem = 0;
 
    // swap if a is small size side .
    if (a < b) {
        let temp = a;
        a = b;
        b = temp;
    }
 
    // Iterate until small size side is
    // greater then 0
    while (b > 0)
    {
        // Update result
        result += parseInt(a/b);
 
        let rem = a % b;
        a = b;
        b = rem;
    }
 
    return result;
}
 
// Driver code
    let n = 13, m = 29;
    document.write(minimumSquare(n, m));
 
</script>

Producción: 

9

Complejidad de tiempo: O(log(max(a,b))) 
Espacio auxiliar: O(1)

Tenga en cuenta que la solución Greedy anterior no siempre produce un resultado óptimo . Por ejemplo, si la entrada es 36 x 30, el algoritmo anterior produciría la salida 6, pero podemos cortar el papel en 5 cuadrados 
1) Tres cuadrados de tamaño 12 x 12 
2) Dos cuadrados de tamaño 18 x 18.

Gracias a Sergey V. Pereslavtsev por señalar el caso anterior.
Este artículo es una contribución de Aarti_Rathi y Kuldeep Singh (kulli_d_coder) . 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.