Tamaño mínimo de array posible con valores de suma y producto dados

Dados dos enteros positivos S y P , la tarea es encontrar el tamaño mínimo posible de la array tal que la suma de los elementos sea S y el producto de los elementos sea P . Si no existe tal array, imprima «-1» .

Ejemplos:

Entrada: S = 5, P = 6
Salida: 2
Explicación: La array válida puede ser {2, 3}, que es de tamaño mínimo.

Entrada: S = 5, P = 100
Salida: -1

Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:

• Usando N números, se puede formar una array de tamaño N con suma S.
• Cualquier valor del producto se puede lograr cuando el valor de P está entre [0, (S/N) ^N ] .

Siga los pasos a continuación para resolver el problema dado:

• Inicialmente, verifique si el valor de S y P es el mismo, luego devuelva 1 ya que el valor S en sí se usa para hacer una array de tamaño mínimo.
• Itere sobre el rango [2, S] usando la variable i , y si el valor de (S/i) >= pow(P, 1/i) entonces imprima el valor de i como el tamaño mínimo resultante de la array formada.
• Después de completar los pasos anteriores, si no hay ningún valor posible que satisfaga los criterios anteriores, imprima «-1» .

A continuación se muestra la implementación del enfoque anterior:

// 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 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

# 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# 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.

<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>

2

Complejidad temporal: O(log P)
Espacio auxiliar: O(1)