Número mínimo de cuboides necesarios para formar un cubo

Dados L , B y H , que denotan la longitud , el ancho y la altura de un paralelepípedo , la tarea es encontrar el número mínimo de paralelepípedos de dimensiones específicas que se pueden colocar juntos para formar un cubo .

Ejemplos:

Entrada: L = 1, B = 1, H = 2
Salida: 4
Explicación: 
Volumen de un paralelepípedo de dimensiones dadas = 1 * 1 * 2 = 2.
Volumen del cubo que se puede formar combinando estos paralelepípedos = 2 * 2 * 2 = 8. 
Por lo tanto, el número de paralelepípedos necesarios = 8 / 2 = 4.

Entrada: L = 2, B = 5, H = 10
Salida: 10

Enfoque ingenuo: encuentre el máximo de las dimensiones dadas y comience a iterar sobre valores enteros a partir del máximo obtenido . Para cada número entero, verifique si puede ser una dimensión posible de un cubo que pueda estar formado por los paralelepípedos dados o no. Para hacerlo, calcula el volumen del cubo y el volumen del paralelepípedo formado por las dimensiones dadas. Comprueba si el primero es divisible por el segundo o no. Si se encuentra que es cierto, imprima el cociente como la respuesta requerida. 

Complejidad temporal: O(L * B * H)
Espacio auxiliar: O(1)

Enfoque eficiente: Para optimizar el enfoque anterior, la idea se basa en la siguiente observación:

• La longitud mínima de un cubo obtenido al combinar cuboides de dimensiones dadas es igual a LCM de L, B y H. Esto se debe a que la dimensión del cubo debe ser divisible por L , B y H .
• Para encontrar el número de paralelepípedos necesarios, calcule el volumen del cubo ( = LCM(L, B, H) ³ ) y el paralelepípedo ( = L * B * H) e imprima ( Volumen del cubo ) / ( Volumen del cuboid ) a la respuesta requerida.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate and
// return LCM of a, b, and c
int find_lcm(int a, int b, int c)
{
    // Find GCD of a and b
    int g = __gcd(a, b);
 
    // Find LCM of a and b
    int LCM1 = (a * b) / g;
 
    // LCM(a, b, c) = LCM(LCM(a, b), c)
    g = __gcd(LCM1, c);
 
    // Finding LCM of a, b, c
    int LCM = (LCM1 * c) / g;
 
    // return LCM(a, b, c)
    return LCM;
}
 
// Function to find the minimum
// number of cuboids required to
// make the volume of a valid cube
void minimumCuboids(int L, int B, int H)
{
    // Find the LCM of L, B, H
    int lcm = find_lcm(L, B, H);
 
    // Volume of the cube
    int volume_cube = lcm * lcm * lcm;
 
    // Volume of the cuboid
    int volume_cuboid = L * B * H;
 
    // Minimum number cuboids required
    // to form a cube
    cout << (volume_cube / volume_cuboid);
}
 
// Driver Code
int main()
{
    // Given dimensions of cuboid
    int L = 1, B = 1, H = 2;
 
    // Function Call
    minimumCuboids(L, B, H);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG
{
 
// Function to calculate and
// return LCM of a, b, and c
static int find_lcm(int a, int b, int c)
{
   
    // Find GCD of a and b
    int g = __gcd(a, b);
 
    // Find LCM of a and b
    int LCM1 = (a * b) / g;
 
    // LCM(a, b, c) = LCM(LCM(a, b), c)
    g = __gcd(LCM1, c);
 
    // Finding LCM of a, b, c
    int LCM = (LCM1 * c) / g;
 
    // return LCM(a, b, c)
    return LCM;
}
 
// Function to find the minimum
// number of cuboids required to
// make the volume of a valid cube
static void minimumCuboids(int L, int B, int H)
{
   
    // Find the LCM of L, B, H
    int lcm = find_lcm(L, B, H);
 
    // Volume of the cube
    int volume_cube = lcm * lcm * lcm;
 
    // Volume of the cuboid
    int volume_cuboid = L * B * H;
 
    // Minimum number cuboids required
    // to form a cube
    System.out.print((volume_cube / volume_cuboid));
}
static int __gcd(int a, int b) 
{ 
    return b == 0 ? a:__gcd(b, a % b);    
}
   
// Driver Code
public static void main(String[] args)
{
   
    // Given dimensions of cuboid
    int L = 1, B = 1, H = 2;
 
    // Function Call
    minimumCuboids(L, B, H);
}
}
 
// This code is contributed by 29AjayKumar

# Python program for the above approach
 
# Function to calculate and
# return LCM of a, b, and c
def find_lcm(a, b, c):
 
    # Find GCD of a and b
    g = __gcd(a, b);
 
    # Find LCM of a and b
    LCM1 = (a * b) // g;
 
    # LCM(a, b, c) = LCM(LCM(a, b), c)
    g = __gcd(LCM1, c);
 
    # Finding LCM of a, b, c
    LCM = (LCM1 * c) // g;
 
    # return LCM(a, b, c)
    return LCM;
 
# Function to find the minimum
# number of cuboids required to
# make the volume of a valid cube
def minimumCuboids(L, B, H):
 
    # Find the LCM of L, B, H
    lcm = find_lcm(L, B, H);
 
    # Volume of the cube
    volume_cube = lcm * lcm * lcm;
 
    # Volume of the cuboid
    volume_cuboid = L * B * H;
 
    # Minimum number cuboids required
    # to form a cube
    print((volume_cube // volume_cuboid));
def __gcd(a, b):
    if(b == 0):
        return a;
    else:
        return __gcd(b, a % b);
 
# Driver Code
if __name__ == '__main__':
 
    # Given dimensions of cuboid
    L = 1; B = 1; H = 2;
 
    # Function Call
    minimumCuboids(L, B, H);
 
# This code contributed by shikhasingrajput

// C# program for the above approach
using System;
class GFG
{
 
// Function to calculate and
// return LCM of a, b, and c
static int find_lcm(int a, int b, int c)
{
   
    // Find GCD of a and b
    int g = __gcd(a, b);
 
    // Find LCM of a and b
    int LCM1 = (a * b) / g;
 
    // LCM(a, b, c) = LCM(LCM(a, b), c)
    g = __gcd(LCM1, c);
 
    // Finding LCM of a, b, c
    int LCM = (LCM1 * c) / g;
 
    // return LCM(a, b, c)
    return LCM;
}
 
// Function to find the minimum
// number of cuboids required to
// make the volume of a valid cube
static void minimumCuboids(int L, int B, int H)
{
   
    // Find the LCM of L, B, H
    int lcm = find_lcm(L, B, H);
 
    // Volume of the cube
    int volume_cube = lcm * lcm * lcm;
 
    // Volume of the cuboid
    int volume_cuboid = L * B * H;
 
    // Minimum number cuboids required
    // to form a cube
    Console.Write((volume_cube / volume_cuboid));
}
static int __gcd(int a, int b) 
{ 
    return b == 0 ? a:__gcd(b, a % b);    
}
   
// Driver Code
public static void Main(String[] args)
{
   
    // Given dimensions of cuboid
    int L = 1, B = 1, H = 2;
 
    // Function Call
    minimumCuboids(L, B, H);
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript program for the above approach
 
// Function to calculate and
// return LCM of a, b, and c
function find_lcm(a, b, c)
{
   
    // Find GCD of a and b
    let g = __gcd(a, b);
 
    // Find LCM of a and b
    let LCM1 = (a * b) / g;
 
    // LCM(a, b, c) = LCM(LCM(a, b), c)
    g = __gcd(LCM1, c);
 
    // Finding LCM of a, b, c
    let LCM = (LCM1 * c) / g;
 
    // return LCM(a, b, c)
    return LCM;
}
 
// Function to find the minimum
// number of cuboids required to
// make the volume of a valid cube
function minimumCuboids(L, B, H)
{
   
    // Find the LCM of L, B, H
    let lcm = find_lcm(L, B, H);
 
    // Volume of the cube
    let volume_cube = lcm * lcm * lcm;
 
    // Volume of the cuboid
    let volume_cuboid = L * B * H;
 
    // Minimum number cuboids required
    // to form a cube
    document.write((volume_cube /
                    volume_cuboid));
}
 
function __gcd(a, b) 
{ 
    return b == 0 ? a : __gcd(b, a % b);    
}
 
// Driver Code
 
// Given dimensions of cuboid
let L = 1, B = 1, H = 2;
 
// Function Call
minimumCuboids(L, B, H);
 
// This code is contributed by splevel62
 
</script>

4

Complejidad de tiempo: O(log(min(L, B, H)))
Espacio auxiliar: O(1)