Given an integer 
. The task is to find all factors of N and print the product of four factors of N such that:
- Sum of the four factors is equal to N.
- Product of the four factors is maximum.
If it is not possible to find 4 such factors then print “Not possible”.
Note: All the four factors can be equal to each other to maximize the product.
Examples:
Input : N = 24 Output : Product -> 1296 All factors are -> 1 2 3 4 6 8 12 24 Choose the factor 6 four times, Therefore, 6+6+6+6 = 24 and product is maximum. Input : N = 100 Output : Product -> 390625 All the factors are -> 1 2 4 5 10 10 20 25 50 100 Choose the factor 25 four times.
An approach which takes a complexity of O(M^3), where M is the number of factors of N has been discussed in the previous post.
An efficient approach of time complexity O(N^2) can be obtained by following the below steps.
- Store all the factors of given number in a container.
- Iterate for all pairs and store their sum in a different container.
- Mark the index (element1 + element2) with pair(element1, element2 to get the elements by which the sum was obtained.
- Iterate for all the pair_sums, and check if n-pair_sum exists in the same container, then both the pairs form the quadruple.
- Use the pair hash array to get the elements by which the pair was formed.
- Store the maximum of all such quadruples, and print it at the end.
Below is the implementation of above approach:
C++
// C++ program to find four factors of N// with maximum product and sum equal to N#include <bits/stdc++.h>using namespace std;// Function to find factors// and to print those four factorsvoid findfactors(int n){ unordered_map<int, int> mpp; vector<int> v, v1; // push all the factors in the container for (int i = 1; i <= sqrt(n); i++) { if (n % i == 0) { v.push_back(i); if (i != (n / i) && i != 1) v.push_back(n / i); } } // number of factors int s = v.size(); // Initial maximum int maxi = -1; // hash-array to mark the // pairs pair<int, int> mp1[n + 5]; for (int i = 0; i < s; i++) { // form all the pair sums for (int j = i; j < s; j++) { // if the pair sum is less than n if (v[i] + v[j] < n) { // push in another container v1.push_back(v[i] + v[j]); // mark the sum with the elements // formed mp1[v[i] + v[j]] = { v[i], v[j] }; // mark in the map that v[i]+v[j] // is present mpp[v[i] + v[j]] = 1; } } } // new size of all the pair sums s = v1.size(); // iterate for all pair sum for (int i = 0; i < s; i++) { // the required part int el = n - (v1[i]); // if the required part is also // present in pair sum if (mpp[el] == 1) { // find the elements with // which the first pair is formed int a = mp1[v1[i]].first; int b = mp1[v1[i]].second; // find the elements with // which the second pair is formed int c = mp1[n - v1[i]].first; int d = mp1[n - v1[i]].second; // check for previous maximum maxi = max(a * b * c * d, maxi); } } if (maxi == -1) cout << "Not Possible\n"; else { cout << "The maximum product is " << maxi << endl; }}// Driver codeint main(){ int n = 50; findfactors(n); return 0;} |
Java
// Java program to find four factors of N// with maximum product and sum equal to Nimport java.util.*;import java.lang.*;import java.io.*;class GFG{ // Function to find factors// and to print those four factorsstatic void findfactors(int n){ HashMap<Integer, Integer> mpp = new HashMap<>(); Vector<Integer> v = new Vector<Integer>(), v1 = new Vector<Integer>(); // push all the factors in the container for (int i = 1; i <= (int)Math.sqrt(n); i++) { if (n % i == 0) { v.add(i); if (i != (n / i) && i != 1) v.add(n / i); } } // number of factors int s = v.size(); // Initial maximum int maxi = -1; // hash-array to mark the // pairs int mp1_first[] = new int[n + 5], mp1_second[] = new int[n + 5]; for (int i = 0; i < s; i++) { // form all the pair sums for (int j = i; j < s; j++) { // if the pair sum is less than n if (v.get(i) + v.get(j) < n) { // push in another container v1.add(v.get(i) + v.get(j)); // mark the sum with the elements // formed mp1_first[v.get(i) + v.get(j)] = v.get(i); mp1_second[v.get(i) + v.get(j)] = v.get(j); // mark in the map that // v.get(i)+v.get(j) is present mpp.put(v.get(i) + v.get(j), 1); } } } // new size of all the pair sums s = v1.size(); // iterate for all pair sum for (int i = 0; i < s; i++) { // the required part int el = n - (v1.get(i)); // if the required part is also // present in pair sum if (mpp.get(el) != null) { // find the elements with // which the first pair is formed int a = mp1_first[v1.get(i)]; int b = mp1_second[v1.get(i)]; // find the elements with // which the second pair is formed int c = mp1_first[n - v1.get(i)]; int d = mp1_second[n - v1.get(i)]; // check for previous maximum maxi = Math.max(a * b * c * d, maxi); } } if (maxi == -1) System.out.println("Not Possible"); else { System.out.println("The maximum product" + " is " + maxi); }}// Driver codepublic static void main(String args[]){ int n = 50; findfactors(n);}}// This code is contributed by Arnab Kundu |
Python3
# Python3 program to find four factors of N# with maximum product and sum equal to Nfrom math import sqrt, ceil, floor# Function to find factors# and to print those four factorsdef findfactors(n): mpp = dict() v = [] v1 = [] # push all the factors in the container for i in range(1,ceil(sqrt(n)) + 1): if (n % i == 0): v.append(i) if (i != (n // i) and i != 1): v.append(n // i) # number of factors s = len(v) # Initial maximum maxi = -1 # hash-array to mark the # pairs mp1 = [0]*(n + 5) for i in range(s): # form all the pair sums for j in range(i, s): # if the pair sum is less than n if (v[i] + v[j] < n): # push in another container v1.append(v[i] + v[j]) # mark the sum with the elements # formed mp1[v[i] + v[j]] =[v[i], v[j]] # mark in the map that v[i]+v[j] # is present mpp[v[i] + v[j]] = 1 # new size of all the pair sums s = len(v1) # iterate for all pair sum for i in range(s): # the required part el = n - (v1[i]) # if the required part is also # present in pair sum if (el in mpp): # find the elements with # which the first pair is formed a = mp1[v1[i]][0] b = mp1[v1[i]][1] # find the elements with # which the second pair is formed c = mp1[n - v1[i]][0] d = mp1[n - v1[i]][1] # check for previous maximum maxi = max(a * b * c * d, maxi) if (maxi == -1): print("Not Possible") else : print("The maximum product is ", maxi)# Driver coden = 50findfactors(n)# This code is contributed by mohit kumar 29 |
C#
// C# program to find four factors of N// with maximum product and sum equal to Nusing System;using System.Collections.Generic;class GFG{ // Function to find factors// and to print those four factorsstatic void findfactors(int n){ Dictionary<int, int> mpp = new Dictionary<int,int>(); List<int> v = new List<int>(), v1 = new List<int>(); // push all the factors in the container for (int i = 1; i <= (int)Math.Sqrt(n); i++) { if (n % i == 0) { v.Add(i); if (i != (n / i) && i != 1) v.Add(n / i); } } // number of factors int s = v.Count; // Initial maximum int maxi = -1; // hash-array to mark the // pairs int []mp1_first = new int[n + 5]; int []mp1_second = new int[n + 5]; for (int i = 0; i < s; i++) { // form all the pair sums for (int j = i; j < s; j++) { // if the pair sum is less than n if (v[i] + v[j] < n) { // push in another container v1.Add(v[i] + v[j]); // mark the sum with the elements // formed mp1_first[v[i] + v[j]] = v[i]; mp1_second[v[i] + v[j]] = v[j]; // mark in the map that // v[i]+v[j] is present mpp.Add(v[i] + v[j], 1); } } } // new size of all the pair sums s = v1.Count; // iterate for all pair sum for (int i = 0; i < s; i++) { // the required part int el = n - (v1[i]); // if the required part is also // present in pair sum if (mpp.ContainsKey(el)) { // find the elements with // which the first pair is formed int a = mp1_first[v1[i]]; int b = mp1_second[v1[i]]; // find the elements with // which the second pair is formed int c = mp1_first[n - v1[i]]; int d = mp1_second[n - v1[i]]; // check for previous maximum maxi = Math.Max(a * b * c * d, maxi); } } if (maxi == -1) Console.WriteLine("Not Possible"); else { Console.WriteLine("The maximum product" + " is " + maxi); }}// Driver codepublic static void Main(String []args){ int n = 50; findfactors(n);}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// Javascript program to find four factors of N// with maximum product and sum equal to N// Function to find factors// and to print those four factorsfunction findfactors(n){ let mpp = new Map(); let v = []; let v1 = []; // push all the factors in the container for (let i = 1; i <= Math.floor(Math.sqrt(n)); i++) { if (n % i == 0) { v.push(i); if (i != Math.floor(n / i) && i != 1) v.push(Math.floor(n / i)); } } // number of factors let s = v.length; // Initial maximum let maxi = -1; // hash-array to mark the // pairs let mp1_first = new Array(n + 5), mp1_second = new Array(n + 5); for (let i = 0; i < s; i++) { // form all the pair sums for (let j = i; j < s; j++) { // if the pair sum is less than n if (v[i] + v[j] < n) { // push in another container v1.push(v[i] + v[j]); // mark the sum with the elements // formed mp1_first[v[i] + v[j]] = v[i]; mp1_second[v[i] + v[j]] = v[j]; // mark in the map that // v.get(i)+v.get(j) is present mpp.set(v[i] + v[j], 1); } } } // new size of all the pair sums s = v1.length; // iterate for all pair sum for (let i = 0; i < s; i++) { // the required part let el = n - (v1[i]); // if the required part is also // present in pair sum if (mpp.get(el) != null) { // find the elements with // which the first pair is formed let a = mp1_first[v1[i]]; let b = mp1_second[v1[i]]; // find the elements with // which the second pair is formed let c = mp1_first[n - v1[i]]; let d = mp1_second[n - v1[i]]; // check for previous maximum maxi = Math.max(a * b * c * d, maxi); } } if (maxi == -1) document.write("Not Possible<br>"); else { document.write("The maximum product" + " is " + maxi); }}// Driver codelet n = 50;findfactors(n); // This code is contributed by patel2127</script> |
Output:
The maximum product is 12500
Time Complexity: O(sqrt(n)+m2) where m is the number of factors of n.
Auxiliary Space: O(m)
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!
Share your thoughts in the comments
