Minimum size of Array possible with given sum and product values
Given two positive integers S and P, the task is to find the minimum possible size of the array such that the sum of elements is S and the product of the elements is P. If there doesn’t exist any such array, then print “-1”.
Examples:
Input: S = 5, P = 6
Output: 2
Explanation: The valid array can be {2, 3}, which is of minimum size.Input: S = 5, P = 100
Output: -1
Approach: The given problem can be solved based on the following observations:
- Using N numbers, an array can be formed of size N having sum S.
- Any product values can be achieved when the value of P is between [0, (S/N)N].
Follow the steps below to solve the given problem:
- Initially check if the value of S and P are the same, then return 1 as the S value itself is used to make a minimum size array.
- Iterate over the range [2, S] using the variable i, and if the value of (S/i) >= pow(P, 1/i) then print the value of i as the resultant minimum size of the array formed.
- After completing the above steps, if there doesn’t any possible value i satisfying the above criteria, then print “-1”.
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 minimum size // of array with sum S and product P int minimumSizeArray( int S, int P) { // Base Case if (S == P) { return 1; } // Iterate through all values of S // and check the mentioned condition for ( int i = 2; i <= S; i++) { double d = i; if ((S / d) >= pow (P, 1.0 / d)) { return i; } } // Otherwise, print "-1" return -1; } // Driver Code int main() { int S = 5, P = 6; cout << minimumSizeArray(S, P); return 0; } |
Java
// Java program for the above approach class GFG{ // Function to find the minimum size // of array with sum S and product P static int minimumSizeArray( int S, int P) { // Base Case if (S == P) { return 1 ; } // Iterate through all values of S // and check the mentioned condition for ( int i = 2 ; i <= S; i++) { double d = i; if ((S / d) >= Math.pow(P, 1.0 / d)) { return i; } } // Otherwise, print "-1" return - 1 ; } // Driver Code public static void main(String args[]) { int S = 5 , P = 6 ; System.out.println(minimumSizeArray(S, P)); } } // This code is contributed by AnkThon |
Python3
# python program for the above approach # Function to find the minimum size # of array with sum S and product P def minimumSizeArray(S, P): # Base Case if (S = = P): return 1 # Iterate through all values of S # and check the mentioned condition for i in range ( 2 , S + 1 ): d = i if ((S / d) > = pow (P, 1.0 / d)): return i # Otherwise, print "-1" return - 1 # Driver Code if __name__ = = "__main__" : S = 5 P = 6 print (minimumSizeArray(S, P)) # This code is contributed by rakeshsahni |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to find the minimum size // of array with sum S and product P static int minimumSizeArray( int S, int P) { // Base Case if (S == P) { return 1; } // Iterate through all values of S // and check the mentioned condition for ( int i = 2; i <= S; i++) { double d = i; if ((S / d) >= Math.Pow(P, 1.0 / d)) { return i; } } // Otherwise, print "-1" return -1; } // Driver Code public static void Main() { int S = 5, P = 6; Console.Write(minimumSizeArray(S, P)); } } // This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the minimum size // of array with sum S and product P function minimumSizeArray(S, P) { // Base Case if (S == P) { return 1; } // Iterate through all values of S // and check the mentioned condition for (let i = 2; i <= S; i++) { let d = i; if ((S / d) >= Math.pow(P, 1.0 / d)) { return i; } } // Otherwise, print "-1" return -1; } // Driver Code let S = 5, P = 6; document.write(minimumSizeArray(S, P)); // This code is contributed by Potta Lokesh </script> |
Output:
2
Time Complexity: O(log P)
Auxiliary Space: O(1)