Given an array arr[], the task is to find the smallest perfect square which is divisible by all the elements of the given array.
Examples:
Input: arr[] = {2, 3, 4, 5, 7}
Output: 44100Input: arr[] = {20, 25, 14, 21, 100, 18, 42, 16, 55}
Output: 21344400
Naive Approach: Check one by one all square number 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 check if there are any prime factors which divide the lcm odd number of times. If there are such factors, multiply LCM by those factors. 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 square// divisible by all the elements of arr[]int minPerfectSquare(int arr[], int n){ ll minPerfectSq; // LCM of all the elements of arr[] ll lcm = lcmOfArray(arr, n); minPerfectSq = (long long)lcm; // Check if 2 divides lcm odd number of times int cnt = 0; while (lcm > 1 && lcm % 2 == 0) { cnt++; lcm /= 2; } if (cnt % 2 != 0) minPerfectSq *= 2; int i = 3; // Check all the numbers that divide lcm // odd number of times while (lcm > 1) { cnt = 0; while (lcm % i == 0) { cnt++; lcm /= i; } // If i divided lcm odd number of times // then multiply the lcm with i if (cnt % 2 != 0) minPerfectSq *= i; i += 2; } // Return the answer return minPerfectSq;}// Driver codeint main(){ int arr[] = { 2, 3, 4, 5, 7 }; int n = sizeof(arr) / sizeof(arr[0]); cout << minPerfectSquare(arr, n); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class solution{// 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 smallest perfect square// divisible by all the elements of arr[]static int minPerfectSquare(int arr[], int n){ int minPerfectSq; // LCM of all the elements of arr[] int lcm = lcmOfArray(arr, n); minPerfectSq = (int)lcm; // Check if 2 divides lcm odd number of times int cnt = 0; while (lcm > 1 && lcm % 2 == 0) { cnt++; lcm /= 2; } if (cnt % 2 != 0) minPerfectSq *= 2; int i = 3; // Check all the numbers that divide lcm // odd number of times while (lcm > 1) { cnt = 0; while (lcm % i == 0) { cnt++; lcm /= i; } // If i divided lcm odd number of times // then multiply the lcm with i if (cnt % 2 != 0) minPerfectSq *= i; i += 2; } // Return the answer return minPerfectSq;}// Driver codepublic static void main(String args[]){ int arr[] = { 2, 3, 4, 5, 7 }; int n = arr.length; System.out.println(minPerfectSquare(arr, n));}}// This code is contributed by// Shashank_Sharma |
Python3
# Python 3 implementation of the approachfrom math import gcd# Function to return the lcm of# all the elements of the arraydef 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(1, n, 1): lcm = int((lcm * arr[i]) / gcd(lcm, arr[i])) # Return the LCM of the array elements return lcm# Function to return the smallest perfect # square divisible by all the elements of arr[]def minPerfectSquare(arr, n): # LCM of all the elements of arr[] lcm = lcmOfArray(arr, n) minPerfectSq = int(lcm) # Check if 2 divides lcm odd # number of times cnt = 0 while (lcm > 1 and lcm % 2 == 0): cnt += 1 lcm /= 2 if (cnt % 2 != 0): minPerfectSq *= 2 i = 3 # Check all the numbers that divide # lcm odd number of times while (lcm > 1): cnt = 0; while (lcm % i == 0): cnt += 1 lcm /= i # If i divided lcm odd number of # times then multiply the lcm with i if (cnt % 2 != 0): minPerfectSq *= i i += 2 # Return the answer return minPerfectSq# Driver codeif __name__ == '__main__': arr = [2, 3, 4, 5, 7] n = len(arr) print(minPerfectSquare(arr, n))# This code is contributed by# Sanjit_Prasad |
C#
// C# implementation of the approachusing System;public 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 smallest perfect square// divisible by all the elements of arr[]static int minPerfectSquare(int []arr, int n){ int minPerfectSq; // LCM of all the elements of arr[] int lcm = lcmOfArray(arr, n); minPerfectSq = (int)lcm; // Check if 2 divides lcm odd number of times int cnt = 0; while (lcm > 1 && lcm % 2 == 0) { cnt++; lcm /= 2; } if (cnt % 2 != 0) minPerfectSq *= 2; int i = 3; // Check all the numbers that divide lcm // odd number of times while (lcm > 1) { cnt = 0; while (lcm % i == 0) { cnt++; lcm /= i; } // If i divided lcm odd number of times // then multiply the lcm with i if (cnt % 2 != 0) minPerfectSq *= i; i += 2; } // Return the answer return minPerfectSq;}// Driver code static public void Main (){ int []arr = { 2, 3, 4, 5, 7 }; int n = arr.Length; Console.WriteLine(minPerfectSquare(arr, n)); }}//This code is contributed by ajit. |
PHP
<?php// PHP implementation of the approach // Function to return the gcd of// two numbers function 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 function 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 // square divisible by all the elements of arr[] function minPerfectSquare($arr, $n) { // LCM of all the elements of arr[] $lcm = lcmOfArray($arr, $n); $minPerfectSq = $lcm; // Check if 2 divides lcm odd // number of times $cnt = 0; while ($lcm > 1 && $lcm % 2 == 0) { $cnt++; $lcm = floor($lcm / 2); } if ($cnt % 2 != 0) $minPerfectSq *= 2; $i = 3; // Check all the numbers that divide // lcm odd number of times while ($lcm > 1) { $cnt = 0; while ($lcm % $i == 0) { $cnt++; $lcm = $lcm / $i; } // If i divided lcm odd number of times // then multiply the lcm with i if ($cnt % 2 != 0) $minPerfectSq *= $i; $i += 2; } // Return the answer return $minPerfectSq; } // Driver code $arr = array( 2, 3, 4, 5, 7 );$n = sizeof($arr);echo minPerfectSquare($arr, $n); // This code is contributed by Ryuga?> |
Javascript
<script> // Javascript implementation of the approach // Function to return the gcd of two numbers function 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 function 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]), 10); // Return the LCM of the array elements return lcm; } // Function to return the smallest perfect square // divisible by all the elements of arr[] function minPerfectSquare(arr, n) { let minPerfectSq; // LCM of all the elements of arr[] let lcm = lcmOfArray(arr, n); minPerfectSq = lcm; // Check if 2 divides lcm odd number of times let cnt = 0; while (lcm > 1 && lcm % 2 == 0) { cnt++; lcm = parseInt(lcm / 2, 10); } if (cnt % 2 != 0) minPerfectSq *= 2; let i = 3; // Check all the numbers that divide lcm // odd number of times while (lcm > 1) { cnt = 0; while (lcm % i == 0) { cnt++; lcm = parseInt(lcm / i, 10); } // If i divided lcm odd number of times // then multiply the lcm with i if (cnt % 2 != 0) minPerfectSq *= i; i += 2; } // Return the answer return minPerfectSq; } let arr = [ 2, 3, 4, 5, 7 ]; let n = arr.length; document.write(minPerfectSquare(arr, n));</script> |
Output
44100
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!
