Given an integer N and an array arr[] having M integers, the task is to find the maximum size of the subset such that the product of all elements of the subset is a factor of N.
Examples:
Input: N = 12, arr[] = {2, 3, 4}
Output: 2
Explanation: The given array 5 subsets such that the product of all elements of the subset is a factor of 12. They are {2}, {3}, {4}, {2, 3} as (2 * 3) = 6, and {3, 4} as (3 * 4) = 12. Therefore, the maximum size of the valid subset is 2.Input: N = 64, arr[] = {1, 2, 4, 8, 16, 32}
Output: 4
Approach: The given problem can be solved using recursion by traversing over all the subsets of the given array arr[] and keeping track of the size of the subsets such that N % (product of subset elements) = 0. Also for the product of the subset elements to be a factor of N, all individual elements of the array arr[] must also be a factor of N. Therefore, the above problem can be solved using the following steps:
- Create a recursive function maximizeSubset(), which calculates the maximum size of the required subset.
- If all the elements of the given array arr[] have been traversed, return 0 which is the base case.
- Iterate over all elements of the array arr[] and if N % arr[i] = 0, include arr[i] in a subset and recursively call for N = N/arr[i] for the remaining array elements.
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 the maximum size of// the subset such that the product of// subset elements is a factor of Nint maximizeSubset(int N, int arr[], int M, int x = 0){ // Base Case if (x == M) { return 0; } // Stores maximum size of valid subset int ans = 0; // Traverse the given array for (int i = x; i < M; i++) { // If N % arr[i] = 0, include arr[i] // in a subset and recursively call // for the remaining array integers if (N % arr[i] == 0) { ans = max( ans, maximizeSubset( N / arr[i], arr, M, x + 1) + 1); } } // Return Answer return ans;}// Driver Codeint main(){ int N = 64; int arr[] = { 1, 2, 4, 8, 16, 32 }; int M = sizeof(arr) / sizeof(arr[0]); cout << maximizeSubset(N, arr, M); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to find the maximum size of // the subset such that the product of // subset elements is a factor of N static int maximizeSubset(int N, int[] arr, int M, int x) { // Base Case if (x == M) { return 0; } // Stores maximum size of valid subset int ans = 0; // Traverse the given array for (int i = x; i < M; i++) { // If N % arr[i] = 0, include arr[i] // in a subset and recursively call // for the remaining array integers if (N % arr[i] == 0) { ans = Math.max(ans, maximizeSubset(N / arr[i], arr, M, x + 1) + 1); } } // Return Answer return ans; } // Driver Code public static void main(String[] args) { int N = 64; int[] arr = { 1, 2, 4, 8, 16, 32 }; int M = arr.length; System.out.println(maximizeSubset(N, arr, M, 0)); }}// This code is contributed by ukasp. |
Python3
# Python Program to implement# the above approach# Function to find the maximum size of# the subset such that the product of# subset elements is a factor of Ndef maximizeSubset(N, arr, M, x=0): # Base Case if (x == M): return 0 # Stores maximum size of valid subset ans = 0 # Traverse the given array for i in range(x, M): # If N % arr[i] = 0, include arr[i] # in a subset and recursively call # for the remaining array integers if (N % arr[i] == 0): ans = max( ans, maximizeSubset( N // arr[i], arr, M, x + 1) + 1) # Return Answer return ans# Driver CodeN = 64arr = [1, 2, 4, 8, 16, 32]M = len(arr)print(maximizeSubset(N, arr, M))# This code is contributed by Saurabh jaiswal |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to find the maximum size of// the subset such that the product of// subset elements is a factor of Nstatic int maximizeSubset(int N, int []arr, int M, int x){ // Base Case if (x == M) { return 0; } // Stores maximum size of valid subset int ans = 0; // Traverse the given array for (int i = x; i < M; i++) { // If N % arr[i] = 0, include arr[i] // in a subset and recursively call // for the remaining array integers if (N % arr[i] == 0) { ans = Math.Max( ans, maximizeSubset( N / arr[i], arr, M, x + 1) + 1); } } // Return Answer return ans;}// Driver Codepublic static void Main(){ int N = 64; int []arr = { 1, 2, 4, 8, 16, 32 }; int M = arr.Length; Console.Write(maximizeSubset(N, arr, M,0));}}// This code is contributed by ipg2016107. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the maximum size of // the subset such that the product of // subset elements is a factor of N function maximizeSubset(N, arr, M, x = 0) { // Base Case if (x == M) { return 0; } // Stores maximum size of valid subset let ans = 0; // Traverse the given array for (let i = x; i < M; i++) { // If N % arr[i] = 0, include arr[i] // in a subset and recursively call // for the remaining array integers if (N % arr[i] == 0) { ans = Math.max( ans, maximizeSubset( Math.floor(N / arr[i]), arr, M, x + 1) + 1); } } // Return Answer return ans; } // Driver Code let N = 64; let arr = [1, 2, 4, 8, 16, 32]; let M = arr.length; document.write(maximizeSubset(N, arr, M)); // This code is contributed by Potta Lokesh </script> |
Output:
4
Time Complexity: O(2N)
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!
