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) 3 ) 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++
// 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
// 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
Python3
# 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#
// 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
Javascript
<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)
Publicación traducida automáticamente
Artículo escrito por prasann7676 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA