Given an array arr[], the task is to find the smallest perfect cube which is divisible by all the elements of the given array.
Examples:
Input: arr[] = {20, 4, 128, 7}
Output: 21952000Input: arr[] = {10, 125, 14, 42, 100}
Output: 9261000
Naive Approach: Check all perfect cubes one by one starting from 1 and select the one which is divisible by all the elements of the array.
Efficient Approach: Find the least common multiple of all the elements of the array and store it in a variable lcm. Find all prime factor of the found LCM.
Now for every prime factor fact which divides the lcm ‘x’ number of times where x % 3 != 0:
- If x % 3 = 2 then update lcm = lcm * fact.
- If x % 3 = 1 then update lcm = lcm * fact2.
Print the updated LCM in the end.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define ll long long int// Function to return the gcd of two numbersll gcd(ll a, ll b){ if (b == 0) return a; else return gcd(b, a % b);}// Function to return the lcm of// all the elements of the arrayll lcmOfArray(int arr[], int n){ if (n < 1) return 0; ll lcm = arr[0]; // To calculate lcm of two numbers // multiply them and divide the result // by gcd of both the numbers for (int i = 1; i < n; i++) lcm = (lcm * arr[i]) / gcd(lcm, arr[i]); // Return the LCM of the array elements return lcm;}// Function to return the smallest perfect cube// divisible by all the elements of arr[]int minPerfectCube(int arr[], int n){ ll minPerfectCube; // LCM of all the elements of arr[] ll lcm = lcmOfArray(arr, n); minPerfectCube = (long long)lcm; int cnt = 0; while (lcm > 1 && lcm % 2 == 0) { cnt++; lcm /= 2; } // If 2 divides lcm cnt number of times if (cnt % 3 == 2) minPerfectCube *= 2; else if (cnt % 3 == 1) minPerfectCube *= 4; int i = 3; // Check all the numbers that divide lcm while (lcm > 1) { cnt = 0; while (lcm % i == 0) { cnt++; lcm /= i; } if (cnt % 3 == 1) minPerfectCube *= i * i; else if (cnt % 3 == 2) minPerfectCube *= i; i += 2; } // Return the answer return minPerfectCube;}// Driver codeint main(){ int arr[] = { 10, 125, 14, 42, 100 }; int n = sizeof(arr) / sizeof(arr[0]); cout << minPerfectCube(arr, n); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{// Function to return the gcd of two numbersstatic int gcd(int a, int b){ if (b == 0) return a; else return gcd(b, a % b);}// Function to return the lcm of// all the elements of the arraystatic int lcmOfArray(int arr[], int n){ if (n < 1) return 0; int lcm = arr[0]; // To calculate lcm of two numbers // multiply them and divide the result // by gcd of both the numbers for (int i = 1; i < n; i++) lcm = (lcm * arr[i]) / gcd(lcm, arr[i]); // Return the LCM of the array elements return lcm;}// Function to return the smaintest perfect cube// divisible by all the elements of arr[]static int minPerfectCube(int arr[], int n){ int minPerfectCube; // LCM of all the elements of arr[] int lcm = lcmOfArray(arr, n); minPerfectCube = lcm; int cnt = 0; while (lcm > 1 && lcm % 2 == 0) { cnt++; lcm /= 2; } // If 2 divides lcm cnt number of times if (cnt % 3 == 2) minPerfectCube *= 2; else if (cnt % 3 == 1) minPerfectCube *= 4; int i = 3; // Check all the numbers that divide lcm while (lcm > 1) { cnt = 0; while (lcm % i == 0) { cnt++; lcm /= i; } if (cnt % 3 == 1) minPerfectCube *= i * i; else if (cnt % 3 == 2) minPerfectCube *= i; i += 2; } // Return the answer return minPerfectCube;}// Driver codepublic static void main(String args[]){ int arr[] = { 10, 125, 14, 42, 100 }; int n = arr.length; System.out.println(minPerfectCube(arr, n));}}// This code is contributed by// Surendra_Gangwar |
Python3
# Python3 implementation of the approach # Function to return the gcd of two numbers def gcd(a, b) : if (b == 0) : return a else : return gcd(b, a % b)# Function to return the lcm of # all the elements of the array def lcmOfArray(arr, n) : if (n < 1) : return 0 lcm = arr[0] # To calculate lcm of two numbers # multiply them and divide the result # by gcd of both the numbers for i in range(n) : lcm = (lcm * arr[i]) // gcd(lcm, arr[i]); # Return the LCM of the array elements return lcm# Function to return the smallest perfect cube # divisible by all the elements of arr[] def minPerfectCube(arr, n) : # LCM of all the elements of arr[] lcm = lcmOfArray(arr, n) minPerfectCube = lcm cnt = 0 while (lcm > 1 and lcm % 2 == 0) : cnt += 1 lcm //= 2 # If 2 divides lcm cnt number of times if (cnt % 3 == 2) : minPerfectCube *= 2 elif (cnt % 3 == 1) : minPerfectCube *= 4 i = 3 # Check all the numbers that divide lcm while (lcm > 1) : cnt = 0 while (lcm % i == 0) : cnt += 1 lcm //= i if (cnt % 3 == 1) : minPerfectCube *= i * i elif (cnt % 3 == 2) : minPerfectCube *= i i += 2 # Return the answer return minPerfectCube # Driver code if __name__ == "__main__" : arr = [ 10, 125, 14, 42, 100 ] n = len(arr) print(minPerfectCube(arr, n)) # This code is contributed by Ryuga |
C#
// C# implementation of the approachusing System;class GFG{// Function to return the gcd of two numbersstatic int gcd(int a, int b){ if (b == 0) return a; else return gcd(b, a % b);}// Function to return the lcm of// all the elements of the arraystatic int lcmOfArray(int []arr, int n){ if (n < 1) return 0; int lcm = arr[0]; // To calculate lcm of two numbers // multiply them and divide the result // by gcd of both the numbers for (int i = 1; i < n; i++) lcm = (lcm * arr[i]) / gcd(lcm, arr[i]); // Return the LCM of the array elements return lcm;}// Function to return the smaintest perfect cube// divisible by all the elements of arr[]static int minPerfectCube(int []arr, int n){ int minPerfectCube; // LCM of all the elements of arr[] int lcm = lcmOfArray(arr, n); minPerfectCube = lcm; int cnt = 0; while (lcm > 1 && lcm % 2 == 0) { cnt++; lcm /= 2; } // If 2 divides lcm cnt number of times if (cnt % 3 == 2) minPerfectCube *= 2; else if (cnt % 3 == 1) minPerfectCube *= 4; int i = 3; // Check all the numbers that divide lcm while (lcm > 1) { cnt = 0; while (lcm % i == 0) { cnt++; lcm /= i; } if (cnt % 3 == 1) minPerfectCube *= i * i; else if (cnt % 3 == 2) minPerfectCube *= i; i += 2; } // Return the answer return minPerfectCube;}// Driver codepublic static void Main(){ int []arr = { 10, 125, 14, 42, 100 }; int n = arr.Length; Console.WriteLine(minPerfectCube(arr, n));}}// This code is contributed by chandan_jnu |
PHP
<?php// PHP implementation of the approach// Function to return the gcd of two numbersfunction gcd($a, $b){ if ($b == 0) return $a; else return gcd($b, $a % $b);}// Function to return the lcm of// all the elements of the arrayfunction lcmOfArray(&$arr, $n){ if ($n < 1) return 0; $lcm = $arr[0]; // To calculate lcm of two numbers // multiply them and divide the result // by gcd of both the numbers for ($i = 1; $i < $n; $i++) $lcm = ($lcm * $arr[$i]) / gcd($lcm, $arr[$i]); // Return the LCM of the array elements return $lcm;}// Function to return the smallest perfect cube// divisible by all the elements of arr[]function minPerfectCube(&$arr, $n){ // LCM of all the elements of arr[] $lcm = lcmOfArray($arr, $n); $minPerfectCube = $lcm; $cnt = 0; while ($lcm > 1 && $lcm % 2 == 0) { $cnt++; $lcm /= 2; } // If 2 divides lcm cnt number of times if ($cnt % 3 == 2) $minPerfectCube *= 2; else if ($cnt % 3 == 1) $minPerfectCube *= 4; $i = 3; // Check all the numbers that divide lcm while ($lcm > 1) { $cnt = 0; while ($lcm % $i == 0) { $cnt++; $lcm /= $i; } if ($cnt % 3 == 1) $minPerfectCube *= $i * $i; else if ($cnt % 3 == 2) $minPerfectCube *= $i; $i += 2; } // Return the answer return $minPerfectCube;}// Driver code$arr = array(10, 125, 14, 42, 100 );$n = sizeof($arr);echo(minPerfectCube($arr, $n));// This code is contributed by Shivi_Aggarwal?> |
Javascript
<script>// Javascript implementation of the approach// Function to return the gcd of two numbersfunction gcd(a, b){ if (b == 0) return a; else return gcd(b, a % b);}// Function to return the lcm of// all the elements of the arrayfunction lcmOfArray(arr, n){ if (n < 1) return 0; let lcm = arr[0]; // To calculate lcm of two numbers // multiply them and divide the result // by gcd of both the numbers for (let i = 1; i < n; i++) lcm = parseInt((lcm * arr[i]) / gcd(lcm, arr[i])); // Return the LCM of the array elements return lcm;}// Function to return the smallest perfect cube// divisible by all the elements of arr[]function minPerfectCube(arr, n){ let minPerfectCube; // LCM of all the elements of arr[] let lcm = lcmOfArray(arr, n); minPerfectCube = lcm; let cnt = 0; while (lcm > 1 && lcm % 2 == 0) { cnt++; lcm = parseInt(lcm/2); } // If 2 divides lcm cnt number of times if (cnt % 3 == 2) minPerfectCube *= 2; else if (cnt % 3 == 1) minPerfectCube *= 4; let i = 3; // Check all the numbers that divide lcm while (lcm > 1) { cnt = 0; while (lcm % i == 0) { cnt++; lcm = parseInt(lcm/i); } if (cnt % 3 == 1) minPerfectCube *= i * i; else if (cnt % 3 == 2) minPerfectCube *= i; i += 2; } // Return the answer return minPerfectCube;}// Driver codelet arr = [ 10, 125, 14, 42, 100 ];let n = arr.length;document.write(minPerfectCube(arr, n));</script> |
Output
9261000
Complexity Analysis:
- Time Complexity: O(n * log(arr[i])
- Auxiliary Space: O(1), since no extra space has been taken.
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!
