Given an array arr[] consisting of N positive integers, the task is to find the minimum possible length of a rod that can be cut into N equal parts such that every ith part can be cut into arr[i] equal parts.
Examples:
Input: arr[] = {1, 2}
Output: 4
Explanation:
Consider the length of the rod as 4. Then it can be divided in 2 equal parts, each having length 2.
Now, part 1 can be divided in arr[0](= 1) equal parts of length 2.
Part 2 can be divided in arr[1](= 2) equal parts of length 1.
Therefore, the minimum length of the rod must be 4.Input: arr[] = {1, 1}
Output: 2
Naive Approach: The given problem can be solved based on the following observations:
- Consider the minimum length of the rod is X, then this rod is cut into N equal parts and the length of each part will be X/N.
- Now each N parts will again be cut down as follows:
- Part 1 will be cut into arr[0] equal where each part has a length say a1.
- Part 2 will be cut into arr[1] equal where each part has a length say a2.
- Part 3 will be cut into arr[2] equal where each part has a length say a3.
- .
- .
- .
- and so on.
- Now, the above relation can also be written as:
X/N = arr[0]*a1 = arr[1]*a2 = … = arr[N – 1]*aN.
- Therefore, the minimum length of the rod is given by:
N*lcm (arr[0]*a1, arr[1]*a2, …, arr[N – 1]*aN)
From the above observations, print the value of the product of N and the LCM of the given array arr[] as the resultant minimum length of the rod.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find GCD// of two numbers a and bint 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 arrayint 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 partsvoid minimumRod(int A[], int N){ // Print the result cout << N * findlcm(A, N);}// Driver Codeint main(){ int arr[] = { 1, 2 }; int N = sizeof(arr) / sizeof(arr[0]); minimumRod(arr, N); return 0;} |
Java
// Java program for the above approachimport 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 bdef 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 arraydef 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 partsdef minimumRod(A, N): # Print the result print(int(N * findlcm(A, N)))# Driver Codearr = [ 1, 2 ]N = len(arr)minimumRod(arr, N)# This code is contributed by sanjoy_62 |
C#
// C# program for the above approachusing 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> |
Output:
4
Time Complexity: O(N*log M) where M is the maximum element of the array.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
