Longitud mínima de una barra que se puede dividir en N partes iguales que se pueden dividir en un número determinado de partes iguales

Posted on by Rudeus Greyrat

Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar la longitud mínima posible de una barra que se puede cortar en N partes iguales de modo que cada i -ésima parte se pueda cortar en arr[i] partes iguales.

Ejemplos:

Entrada: arr[] ={1, 2}
Salida: 4
Explicación:
Considere la longitud de la barra como 4. Luego se puede dividir en 2 partes iguales, cada una con una longitud de 2.
Ahora, la parte 1 se puede dividir en arr[ 0](= 1) partes iguales de longitud 2.
La parte 2 se puede dividir en arr[1](= 2) partes iguales de longitud 1.
Por tanto, la longitud mínima de la varilla debe ser 4.

Entrada: arr[]= {1, 1}
Salida: 2

Enfoque ingenuo: el problema dado se puede resolver en función de las siguientes observaciones:

  • Considere que la longitud mínima de la barra es X , luego esta barra se corta en N partes iguales y la longitud de cada parte será X/N .
  • Ahora, cada N partes se reducirá nuevamente de la siguiente manera:
    • La parte 1 se cortará en arr[0] iguales donde cada parte tiene una longitud, digamos 1 .
    • La parte 2 se cortará en arr[1] iguales donde cada parte tiene una longitud, digamos 2 .
    • La parte 3 se cortará en arr[2] iguales donde cada parte tiene una longitud, por ejemplo, 3 .
    • .
    • .
    • .
    • y así.
  • Ahora, la relación anterior también se puede escribir como:

X/N = arr[0]*a 1 = arr[1]*a 2 = … = arr[N – 1]*a N .

  • Por lo tanto, la longitud mínima de la barra viene dada por:

N*lcm (arr[0]*a 1 , arr[1]*a 2 , …, arr[N – 1]*a N )

A partir de las observaciones anteriores, imprima el valor del producto de N y el LCM del arreglo dado arr[] como la longitud mínima resultante de la barra.

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 find GCD
// of two numbers a and b
int gcd(int a, int b)
{
    // Base Case
    if (b == 0)
        return a;
 
    // Find GCD recursively
    return gcd(b, a % b);
}
 
// Function to find the LCM
// of the resultant array
int findlcm(int arr[], int n)
{
    // Initialize a variable ans
    // as the first element
    int ans = arr[0];
 
    // Traverse the array
    for (int i = 1; i < n; i++) {
 
        // Update LCM
        ans = (((arr[i] * ans))
               / (gcd(arr[i], ans)));
    }
 
    // Return the minimum
    // length of the rod
    return ans;
}
 
// Function to find the minimum length
// of the rod that can be divided into
// N equals parts and each part can be
// further divided into arr[i] equal parts
void minimumRod(int A[], int N)
{
    // Print the result
    cout << N * findlcm(A, N);
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2 };
    int N = sizeof(arr) / sizeof(arr[0]);
    minimumRod(arr, N);
 
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
public class GFG {
 
    // Function to find GCD
    // of two numbers a and b
    static int gcd(int a, int b)
    {
        // Base Case
        if (b == 0)
            return a;
 
        // Find GCD recursively
        return gcd(b, a % b);
    }
 
    // Function to find the LCM
    // of the resultant array
    static int findlcm(int arr[], int n)
    {
        // Initialize a variable ans
        // as the first element
        int ans = arr[0];
 
        // Traverse the array
        for (int i = 1; i < n; i++) {
 
            // Update LCM
            ans = (((arr[i] * ans)) / (gcd(arr[i], ans)));
        }
 
        // Return the minimum
        // length of the rod
        return ans;
    }
 
    // Function to find the minimum length
    // of the rod that can be divided into
    // N equals parts and each part can be
    // further divided into arr[i] equal parts
    static void minimumRod(int A[], int N)
    {
        // Print the result
        System.out.println(N * findlcm(A, N));
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 1, 2 };
        int N = arr.length;
        minimumRod(arr, N);
    }
}
 
// This code is contributed by Kingash.

Python3

# Python3 program for the above approach
 
# Function to find GCD
# of two numbers a and b
def gcd(a, b):
     
    # Base Case
    if (b == 0):
        return a
         
    # Find GCD recursively
    return gcd(b, a % b)
 
# Function to find the LCM
# of the resultant array
def findlcm(arr, n):
     
    # Initialize a variable ans
    # as the first element
    ans = arr[0]
     
    # Traverse the array
    for i in range(n):
         
        # Update LCM
        ans = (((arr[i] * ans)) /
            (gcd(arr[i], ans)))
     
    # Return the minimum
    # length of the rod
    return ans
 
# Function to find the minimum length
# of the rod that can be divided into
# N equals parts and each part can be
# further divided into arr[i] equal parts
def minimumRod(A, N):
     
    # Print the result
    print(int(N * findlcm(A, N)))
 
# Driver Code
arr = [ 1, 2 ]
N = len(arr)
 
minimumRod(arr, N)
 
# This code is contributed by sanjoy_62

C#

// C# program for the above approach
using System;
class GFG
{
   
    // Function to find GCD
    // of two numbers a and b
    static int gcd(int a, int b)
    {
       
        // Base Case
        if (b == 0)
            return a;
 
        // Find GCD recursively
        return gcd(b, a % b);
    }
 
    // Function to find the LCM
    // of the resultant array
    static int findlcm(int[] arr, int n)
    {
       
        // Initialize a variable ans
        // as the first element
        int ans = arr[0];
 
        // Traverse the array
        for (int i = 1; i < n; i++) {
 
            // Update LCM
            ans = (((arr[i] * ans)) / (gcd(arr[i], ans)));
        }
 
        // Return the minimum
        // length of the rod
        return ans;
    }
 
    // Function to find the minimum length
    // of the rod that can be divided into
    // N equals parts and each part can be
    // further divided into arr[i] equal parts
    static void minimumRod(int[] A, int N)
    {
       
        // Print the result
        Console.WriteLine(N * findlcm(A, N));
    }
   
  // Driver code
    static void Main()
    {
        int[] arr = { 1, 2 };
        int N = arr.Length;
        minimumRod(arr, N);
    }
}
 
// This code is contributed by sk944795.

Javascript

<script>
 
// javascript program for the above approach
 
    // Function to find GCD
    // of two numbers a and b
    function gcd(a, b)
    {
        // Base Case
        if (b == 0)
            return a;
  
        // Find GCD recursively
        return gcd(b, a % b);
    }
  
    // Function to find the LCM
    // of the resultant array
    function findlcm(arr, n)
    {
        // Initialize a variable ans
        // as the first element
        let ans = arr[0];
  
        // Traverse the array
        for (let i = 1; i < n; i++) {
  
            // Update LCM
            ans = (((arr[i] * ans)) / (gcd(arr[i], ans)));
        }
  
        // Return the minimum
        // length of the rod
        return ans;
    }
  
    // Function to find the minimum length
    // of the rod that can be divided into
    // N equals parts and each part can be
    // further divided into arr[i] equal parts
    function minimumRod(A, N)
    {
        // Print the result
        document.write(N * findlcm(A, N));
    }
 
// Driver Code
 
    let arr = [ 1, 2 ];
    let N = arr.length;
    minimumRod(arr, N);
     
 
</script>
Producción: 

4

 

Complejidad de tiempo: O(N*log M) donde M es el elemento máximo de la array .
Espacio Auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por grand_master y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *