# Maximum size of subset such that product of all subset elements is a factor of N

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:2Explaination: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 N` `int` `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 Code` `int` `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 approach` `import` `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 N` `def` `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 Code` `N ` `=` `64` `arr ` `=` `[` `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 approach` `using` `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 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()` `{` ` ` `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(2^{N})**Auxiliary Space:** O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.