Given an array arr[] containing positive integers, the task is to find the minimum number of operations to be done on the array to make every number of the array a superpower.
In each operation, we can multiply any element of the array with an integer.
A superpower is defined as a number in the array which when multiplied by any other number in the array apart from itself forms a perfect square.
Examples:
Input: arr[] = {2, 2, 2}
Output: 0
Explanation:
We don’t need to perform any operation on the array because on selecting any element (2) and multiplying it with any element in some other index (2), we get a perfect square (4).
Input: arr[] = {2, 4, 6}
Output: 2
Explanation:
We need to perform the following two operations:
First, we multiply the element at index 1 with integer 2. The array becomes {2, 8, 6}.
Second, we multiply the element at index 2 with integer 3. The array becomes {2, 8, 18}.
Now, all the elements have become a superpower. The multiplication of any two numbers from the array gives a perfect square.
That is, 2 * 8 = 16, 2 * 16 = 36 and 8 * 18 = 144.
Approach: Since we need to check the prime factors for all the numbers, the idea is to first precompute the unique prime factors of all the numbers and store it in a hashmap. Then, we create a variable to store the number of times that the prime factor appears in every single element of the array. We also need to observe that we need to find the minimum number of steps to convert the array. Therefore, we calculate the number of odd in the vector and the number of even prime factors, and whichever is the minimum, that will be the answer. The following steps can be computed to find the answer:
- We first need to calculate the spf[] array. This is the array in which the smallest prime factor for all the elements is stored.
- Then, we need to find the unique prime factors and store it in the hashmap.
- Now, traverse the hash map to find the unique prime factors of a number and iterate over the elements in the given array to calculate the frequency of the prime factors.
- Now, two variables are initialized which stores the frequency of the prime number whose occurrence is even and another store the frequency of the prime numbers which is odd.
- Now, we need to add the minimum of the two variables in our final variable which is the minimum operation to attain superpower for that prime number.
- Repeat the above steps for all the numbers in the array.
Below is the implementation of the above approach:
C++
// C++ program to find the minimum // number of steps to modify the // array such that the product // of any two numbers in the // array is a perfect square #include <iostream> #include <unordered_map> #include <vector> using namespace std; // Function to find the smallest // prime factor of the elements void spf_array(int spf[]) { // Initializing the first element // of the array spf[1] = 1; // Loop to add the remaining // elements to the array for (int i = 2; i < 1000; i++) // Marking the smallest prime // factor for every // number to be itself spf[i] = i; // Separately marking spf for // every even number as 2 for (int i = 4; i < 1000; i += 2) spf[i] = 2; for (int i = 3; i * i < 1000; i++) { // Checking if i is prime if (spf[i] == i) { // Marking SPF for all the // numbers divisible by i for (int j = i * i; j < 1000; j += i) // Marking spf[j] if it is not // previously marked if (spf[j] == j) spf[j] = i; } } } // Function to find the minimum // number of steps to modify the // array such that the product // of any two numbers in the // array is a perfect square int minimum_operation(int b[], int d, int spf[]) { // Map created to store // the unique prime numbers unordered_map<int, int> m; int i = 0; // Variable to store the // minimum number of operations int c = 0; // Loop to store every // unique prime number for (i = 0; i < d; i++) { int x = b[i]; while (x != 1) { x = x / spf[x]; if (m[spf[x]] == 0) { m[spf[x]] = 1; } } } // Erasing 1 as a key because // it is not a prime number m.erase(1); // Iterating through the hash for (auto x : m) { // Two variables used for // counting the frequency // of prime is even or odd int e = 0, o = 0; // First prime number int j = x.first; // Iterating the number D for (i = 0; i < d; i++) { // check if prime is a // factor of the element // in the array if (b[i] % j == 0) { int h = 0; int g = b[i]; // Loop for calculating the // frequency of the element while (g != 0) { if (g % j != 0) { break; } g = g / j; h = h + 1; } // Check for frequency // odd or even if (h % 2 == 0) { e = e + 1; } else { o = o + 1; } } else { // If it is not a factor of the // element, then it is automatically // even e = e + 1; } } // Storing the minimum of two variable // even or odd c = c + min(o, e); } return c; } // Driver code int main() { int spf[1001]; // Input array int b[] = { 1, 4, 6 }; // Creating shortest prime // factorisation array int d = sizeof(b) / sizeof(b[0]); spf_array(spf); cout << minimum_operation(b, d, spf) << endl; } |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG{ // Function to find the smallest// prime factor of the elementsstatic void spf_array(int spf[]){ // Initializing the first element // of the array spf[1] = 1; // Loop to add the remaining // elements to the array for(int i = 2; i < 1000; i++) // Marking the smallest prime // factor for every // number to be itself spf[i] = i; // Separately marking spf for // every even number as 2 for(int i = 4; i < 1000; i += 2) spf[i] = 2; for(int i = 3; i * i < 1000; i++) { // Checking if i is prime if (spf[i] == i) { // Marking SPF for all the // numbers divisible by i for(int j = i * i; j < 1000; j += i) // Marking spf[j] if it is not // previously marked if (spf[j] == j) spf[j] = i; } }}// Function to find the minimum// number of steps to modify the// array such that the product// of any two numbers in the// array is a perfect squarestatic int minimum_operation(int b[], int d, int spf[]){ // Map created to store // the unique prime numbers Map<Integer, Integer> m=new HashMap<>(); int i = 0; // Variable to store the // minimum number of operations int c = 0; // Loop to store every // unique prime number for(i = 0; i < d; i++) { int x = b[i]; while (x != 1) { x = x / spf[x]; if (m.get(spf[x]) == null) { m.put(spf[x],1); } } } // Erasing 1 as a key because // it is not a prime number m.remove(1); // Iterating through the hash for(Map.Entry<Integer, Integer> x : m.entrySet()) { // Two variables used for // counting the frequency // of prime is even or odd int e = 0, o = 0; // First prime number int j = x.getKey(); // Iterating the number D for(i = 0; i < d; i++) { // Check if prime is a // factor of the element // in the array if (b[i] % j == 0) { int h = 0; int g = b[i]; // Loop for calculating the // frequency of the element while (g != 0) { if (g % j != 0) { break; } g = g / j; h = h + 1; } // Check for frequency // odd or even if (h % 2 == 0) { e = e + 1; } else { o = o + 1; } } else { // If it is not a factor of the // element, then it is automatically // even e = e + 1; } } // Storing the minimum of two variable // even or odd c = c + Math.min(o, e); } return c;}// Driver Codepublic static void main (String[] args){ int[] spf = new int[1001]; // Input array int b[] = { 1, 4, 6 }; // Creating shortest prime // factorisation array int d = b.length; spf_array(spf); System.out.print(minimum_operation(b, d, spf));}}// This code is contributed by offbeat |
Python3
# Python program to find the minimum # number of steps to modify the # array such that the product # of any two numbers in the # array is a perfect square # Function to find the smallest # prime factor of the elements def spf_array(spf): # Initializing the first element # of the array spf[1] = 1; # Loop to add the remaining # elements to the array for i in range(2, 1000): # Marking the smallest prime # factor for every # number to be itself spf[i] = i; # Separately marking spf for # every even number as 2 for i in range(4, 1000, 2): spf[i] = 2; for i in range(3, (int)(1000 ** 0.5), 1): # Checking if i is prime if (spf[i] == i): # Marking SPF for all the # numbers divisible by i for j in range(i * i, 1000, i): # Marking spf[j] if it is not # previously marked if (spf[j] == j): spf[j] = i; # Function to find the minimum # number of steps to modify the # array such that the product # of any two numbers in the # array is a perfect square def minimum_operation( b, d, spf) : # Map created to store # the unique prime numbers m = dict(); i = 0; # Variable to store the # minimum number of operations c = 0; # Loop to store every # unique prime number for i in range(d): x = b[i]; while (x != 1): x = (x // spf[x]); if (spf[x] not in m): m[spf[x]] = 1 # Erasing 1 as a key because # it is not a prime number m.pop(1); # Iterating through the hash for key in m.keys(): # Two variables used for # counting the frequency # of prime is even or odd e = 0 o = 0 # First prime number j = key; # Iterating the number D for i in range(d): # check if prime is a # factor of the element # in the array if (b[i] % j == 0): h = 0; g = b[i]; # Loop for calculating the # frequency of the element while (g != 0): if (g % j != 0): break; g = g // j h = h + 1; # Check for frequency # odd or even if (h % 2 == 0): e = e + 1; else : o = o + 1; else: # If it is not a factor of the # element, then it is automatically # even e = e + 1; # Storing the minimum of two variable # even or odd c = c + min(o, e); return c; # Driver code spf = [0] * (1001)# Input array b = [1, 4, 6 ]; # Creating shortest prime # factorisation array d = len(b); spf_array(spf); print( minimum_operation(b, d, spf) );# This code is contributed by entertain2022. |
C#
// C# program for // the above approachusing System;using System.Collections.Generic;class GFG{ // Function to find the smallest// prime factor of the elementsstatic void spf_array(int []spf){ // Initializing the first element // of the array spf[1] = 1; // Loop to add the remaining // elements to the array for(int i = 2; i < 1000; i++) // Marking the smallest prime // factor for every // number to be itself spf[i] = i; // Separately marking spf for // every even number as 2 for(int i = 4; i < 1000; i += 2) spf[i] = 2; for(int i = 3; i * i < 1000; i++) { // Checking if i is prime if (spf[i] == i) { // Marking SPF for all the // numbers divisible by i for(int j = i * i; j < 1000; j += i) // Marking spf[j] if it is not // previously marked if (spf[j] == j) spf[j] = i; } }}// Function to find the minimum// number of steps to modify the// array such that the product// of any two numbers in the// array is a perfect squarestatic int minimum_operation(int []b, int d, int []spf){ // Map created to store // the unique prime numbers Dictionary<int, int> m = new Dictionary<int, int>(); int i = 0; // Variable to store the // minimum number of operations int c = 0; // Loop to store every // unique prime number for(i = 0; i < d; i++) { int x = b[i]; while (x != 1) { x = x / spf[x]; if (!m.ContainsKey(spf[x])) { m.Add(spf[x], 1); } } } // Erasing 1 as a key because // it is not a prime number m.Remove(1); // Iterating through the hash foreach(KeyValuePair<int, int> x in m) { // Two variables used for // counting the frequency // of prime is even or odd int e = 0, o = 0; // First prime number int j = x.Key; // Iterating the number D for(i = 0; i < d; i++) { // Check if prime is a // factor of the element // in the array if (b[i] % j == 0) { int h = 0; int g = b[i]; // Loop for calculating the // frequency of the element while (g != 0) { if (g % j != 0) { break; } g = g / j; h = h + 1; } // Check for frequency // odd or even if (h % 2 == 0) { e = e + 1; } else { o = o + 1; } } else { // If it is not a factor of the // element, then it is automatically // even e = e + 1; } } // Storing the minimum of two variable // even or odd c = c + Math.Min(o, e); } return c;}// Driver Codepublic static void Main(String[] args){ int[] spf = new int[1001]; // Input array int []b = {1, 4, 6}; // Creating shortest prime // factorisation array int d = b.Length; spf_array(spf); Console.Write(minimum_operation(b, d, spf));}}// This code is contributed by shikhasingrajput |
Javascript
<script>// JavaScript program to find the minimum // number of steps to modify the // array such that the product // of any two numbers in the // array is a perfect square // Function to find the smallest // prime factor of the elements function spf_array(spf) { // Initializing the first element // of the array spf[1] = 1; // Loop to add the remaining // elements to the array for (var i = 2; i < 1000; i++) // Marking the smallest prime // factor for every // number to be itself spf[i] = i; // Separately marking spf for // every even number as 2 for (var i = 4; i < 1000; i += 2) spf[i] = 2; for (var i = 3; i * i < 1000; i++) { // Checking if i is prime if (spf[i] == i) { // Marking SPF for all the // numbers divisible by i for (var j = i * i; j < 1000; j += i) // Marking spf[j] if it is not // previously marked if (spf[j] == j) spf[j] = i; } } } // Function to find the minimum // number of steps to modify the // array such that the product // of any two numbers in the // array is a perfect square function minimum_operation( b, d, spf) { // Map created to store // the unique prime numbers var m = new Map(); var i = 0; // Variable to store the // minimum number of operations var c = 0; // Loop to store every // unique prime number for (i = 0; i < d; i++) { var x = b[i]; while (x != 1) { x = parseInt(x / spf[x]); if (!m.has(spf[x])) { m.set(spf[x], 1); } } } // Erasing 1 as a key because // it is not a prime number m.delete(1); // Iterating through the hash m.forEach((value, key) => { // Two variables used for // counting the frequency // of prime is even or odd var e = 0, o = 0; // First prime number var j = key; // Iterating the number D for (i = 0; i < d; i++) { // check if prime is a // factor of the element // in the array if (b[i] % j == 0) { var h = 0; var g = b[i]; // Loop for calculating the // frequency of the element while (g != 0) { if (g % j != 0) { break; } g = parseInt(g / j); h = h + 1; } // Check for frequency // odd or even if (h % 2 == 0) { e = e + 1; } else { o = o + 1; } } else { // If it is not a factor of the // element, then it is automatically // even e = e + 1; } } // Storing the minimum of two variable // even or odd c = c + Math.min(o, e); }); return c; } // Driver code var spf = Array(1001)// Input array var b = [1, 4, 6 ]; // Creating shortest prime // factorisation array var d = b.length; spf_array(spf); document.write( minimum_operation(b, d, spf) );</script> |
Output:
2
Time Complexity: O(N * log(N)), where N is the size of the input array.
Space Complexity: O(n)
The space complexity of the algorithm is O(n), where n is the length of the array. We create an array of size n to store the smallest prime factor of every element of the array.
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!
