Given an array arr[] (where arr[i] lies in the range [2, 30] )of size N, the task is to find the number of subsets such that the product of the elements is not divisible by any perfect square number.
Examples:
Input: arr[] = {2, 4, 3}
Output : 3
Explanation:
Subset1 – {2}
Subset2 – {3}
Subset3 – {2, 3} 6 is not divisible by any perfect square number greater than 1Input: arr[] = { 2, 2, 2 }
Output: 3
Explanation:
{2} subset contains an element at index 0
{2} subset contains an element at index 1
{2} subset contains an element at index 2
Approach: The problem can be solved based on the following idea:
Suppose the product is X. X can be written as X = p1e1 * p2e2 * p3e3 * . . . where pi is a prime number and ei is the exponent for the prime number pi. So we can conclude that all the prime numbers should have exponent 1. Otherwise, X would be divisible by a perfect square.
As the constraint for arr[i] is 30, there are only 10 primes under that {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}. So total 1024 numbers are possible. The task is to find the subsets with product being any of these numbers.
Follow the steps mentioned below to implement the idea:
- Create a map and store the frequency of all elements of the array.
- Create an array to store all the prime numbers less than 30.
- Create a dummy array (say temp[]) and store the numbers that can be made using the primes less than 30.
- Then initialize a variable ans to store the result.
- Start a loop and iterate over the temp array.
- Start another loop from j = 1 to j*j < i to count perfect squares.
- Inside this loop count the number of subsets that have product as i and increment the answer.
- Start another loop from j = 1 to j*j < i to count perfect squares.
- Return the ans with modulo.
Below is the Implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;long mod = 1000000007;// Function to find the number of subsetsint findNumbers(vector<int>& arr){ int n = arr.size(); // Map to find the frequency // of each number in the array unordered_map<long, long> mp; for (auto i : arr) mp[i]++; // Prime numbers less than 30 vector<int> prime = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 }; // Vector to store numbers that can be made // using combination of above prime numbers vector<int> temp; for (int i = 1; i < 1024; i++) { long p = 1; for (int j = 0; j < 11; j++) { if ((i >> j) & 1) p *= prime[j]; } temp.push_back(p); } int ans = 0; for (auto i : temp) { for (int j = 1; j * j < i; j++) { if (i % j == 0) { mp[i] = (mp[i] + mp[j] * mp[i / j]) % mod; } } ans = (ans + mp[i]) % mod; } return ans;}// Driver Codeint main(){ vector<int> arr = { 2, 4, 3 }; // Function call int ans = findNumbers(arr); cout << ans << endl; return 0;} |
Java
// Java code to implement the approachimport java.util.*;class GFG { static long mod = 1000000007; static int findNumbers(List<Integer> arr) { int n = arr.size(); // Map to find the frequency // of each number in the array HashMap<Long, Long> mp = new HashMap<Long, Long>(); for (int i : arr) { if (mp.containsKey((long)i)) mp.put((long)i, mp.get((long)i) + 1); else mp.put((long)i, (long)1); } // Prime numbers less than 30 List<Integer> prime = Arrays.asList( 2, 3, 5, 7, 11, 13, 17, 19, 23, 29); // List to store numbers that can be made // using combination of above prime numbers List<Integer> temp = new ArrayList<Integer>(); for (int i = 1; i < 1024; i++) { long p = 1; for (int j = 0; j < 11; j++) { if ((i >> j) % 2 == 1) p *= prime.get(j); } temp.add((int)p); } int ans = 0; for (int i : temp) { for (int j = 1; j * j < i; j++) { if (i % j == 0) { if (mp.containsKey((long)j) && mp.containsKey((long)(i / j))) { if (mp.containsKey((long)i)) mp.put((long)i, (mp.get((long)i) + mp.get((long)j) * mp.get(( long)(i / j))) % mod); else mp.put((long)i, (mp.get((long)j) * mp.get((long)(i / j))) % mod); } } } if (mp.containsKey((long)i)) ans = (ans + (int)(mp.get((long)i) % mod)) % (int)mod; } return ans; } public static void main(String[] args) { List<Integer> arr = Arrays.asList(2, 4, 3); // Function call int ans = findNumbers(arr); System.out.println(ans); }}// This code is contributed by Prasad Kandekar(prasad264) |
Python3
import collectionsdef findNumbers(arr): n = len(arr) mp = collections.defaultdict(int) for i in arr: mp[i] += 1 prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] temp = [] for i in range(1, 1024): p = 1 for j in range(11): if (i >> j) & 1: p *= prime[j] temp.append(p) mod = 1000000007 ans = 0 for i in temp: for j in range(1, int(i ** 0.5) + 1): if i % j == 0 and j in mp: mp[i] = (mp[i] + mp[j] * mp[i // j]) % mod ans = (ans + mp[i]) % mod return ansarr = [2, 4, 3]ans = findNumbers(arr)print(ans) |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;using System.Linq;class Solution{ static long mod = 1000000007; static int findNumbers(List<int> arr) { int n = arr.Count(); // Map to find the frequency // of each number in the array Dictionary<long, long> mp = new Dictionary<long, long>(); foreach (var i in arr) { if (mp.ContainsKey(i)) mp[i]++; else mp[i] = 1; } // Prime numbers less than 30 List<int> prime = new List<int> { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 }; // Vector to store numbers that can be made // using combination of above prime numbers List<int> temp = new List<int>(); for (int i = 1; i < 1024; i++) { long p = 1; for (int j = 0; j < 11; j++) { if ((i >> j) % 2 == 1) p *= prime[j]; } temp.Add((int)p); } int ans = 0; foreach (var i in temp) { for (int j = 1; j * j < i; j++) { if (i % j == 0) { if (mp.ContainsKey(j) && mp.ContainsKey(i / j)) { if(mp.ContainsKey(i)) mp[i] = (mp[i] + mp[j] * mp[i / j]) % mod; else mp[i] = (mp[j] * mp[i / j]) % mod; } } } if(mp.ContainsKey(i)) ans = (ans + (int)mp[i]) % (int)mod; } return ans; } public static void Main() { List<int> arr = new List<int> { 2, 4, 3 }; // Function call int ans = findNumbers(arr); Console.WriteLine(ans); }}// This code is contributed by Utkarsh Kumar. |
Javascript
// JavaScript code for the above approach let mod = 1000000007; // Function to find the number of subsets function findNumbers(arr) { let n = arr.length; // Map to find the frequency // of each number in the array let mp = new Map(); for (let i of arr) { if (mp.has(i)) { mp.set(i, mp.get(i) + 1) } else { mp.set(i, 1); } } // Prime numbers less than 30 let prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]; // vector to store numbers that can be made // using combination of above prime numbers let temp = []; for (let i = 1; i < 1024; i++) { let p = 1; for (let j = 0; j < 11; j++) { if ((i >> j) & 1) p *= prime[j]; } temp.push(p); } let ans = 1; for (let i of temp) { for (let j = 1; j * j < i; j++) { if (i % j == 0) { if (mp.has(i) && mp.has(j) && mp.has(i / j)) mp.set(i, (mp.get(i) + mp.get(j) * mp.get(Math.floor(i / j))) % mod); } } if (mp.has(i)) ans = (ans % mod + mp.get(i) % mod) % mod; } return ans; } // Driver Code let arr = [2, 4, 3]; // Function call let ans = findNumbers(arr); console.log(ans) // This code is contributed by poojaagarwals2. |
Output
3
Time Complexity: O(1024 * sqrt(X)) where X is largest number in temp
Auxiliary Space: O(210)
Related Articles:
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!
