Encuentre el valor de N cuando F(N) = f(a)+f(b) donde a+b es el mínimo posible y a*b = N

Dado un número entero N , la tarea es encontrar el valor de F(N) si:  

1. F(1) = 0
2. F(2) = 2
3. F(N) = 0, si N es primo impar.
4. F(N) = F(a) + F(b), donde a y b son factores de N y (a + b) es mínimo entre todos los factores. Además, a * b = N

Ejemplos:  

Entrada: N = 5 
Salida: 0 
Dado que 5 es un número primo impar.
Entrada: N = 4 
Salida: 4 
4 se puede escribir como 2 * 2, por lo tanto f(2) + f(2) = 4
Entrada: N = 20 
Salida: 4 
20 se puede escribir como f(4) + f(5 ), y f(4) se puede escribir como f(2) + f(2), que es 4.  

Enfoque : Se pueden seguir los siguientes pasos para resolver el problema:  

• Si N es 1 o 2, la respuesta es 0 o 2 respectivamente.
• Al romper la recurrencia f(n) = f(a) + f(b), obtenemos que es el número de veces que un número es divisible por 2.
• La respuesta para f(n) es 2 * (número de veces que un número es divisible por 2)

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the value of F(N)
int getValueOfF(int n)
{
 
    // Base cases
    if (n == 1)
        return 0;
    if (n == 2)
        return 1;
 
    int cnt = 0;
 
    // Count the number of times a number
    // if divisible by 2
    while (n % 2 == 0) {
        cnt += 1;
        n /= 2;
    }
 
    // Return the summation
    return 2 * cnt;
}
 
// Driver code
int main()
{
    int n = 20;
    cout << getValueOfF(n);
 
    return 0;
}

// Java implementation of the approach
import java.io.*;
 
class GFG
{
     
// Function to return the value of F(N)
static int getValueOfF(int n)
{
 
    // Base cases
    if (n == 1)
        return 0;
    if (n == 2)
        return 1;
 
    int cnt = 0;
 
    // Count the number of times a number
    // if divisible by 2
    while (n % 2 == 0)
    {
        cnt += 1;
        n /= 2;
    }
 
    // Return the summation
    return 2 * cnt;
}
 
// Driver code
public static void main (String[] args)
{
    int n = 20;
    System.out.println (getValueOfF(n));
}
}
 
// This code is contributed by ajit.

# Python3 implementation of the approach
 
# Function to return the value of F(N)
def getValueOfF(n):
 
    # Base cases
    if (n == 1):
        return 0
    if (n == 2):
        return 1
 
    cnt = 0
 
    # Count the number of times a number
    # if divisible by 2
    while (n % 2 == 0):
        cnt += 1
        n /= 2
 
    # Return the summation
    return 2 * cnt
 
# Driver code
n = 20
print(getValueOfF(n))
 
# This code is contributed by mohit kumar

// C# implementation of the approach
using System;
 
class GFG
{
         
// Function to return the value of F(N)
static int getValueOfF(int n)
{
 
    // Base cases
    if (n == 1)
        return 0;
    if (n == 2)
        return 1;
 
    int cnt = 0;
 
    // Count the number of times a number
    // if divisible by 2
    while (n % 2 == 0)
    {
        cnt += 1;
        n /= 2;
    }
 
    // Return the summation
    return 2 * cnt;
}
 
// Driver code
static public void Main ()
{
    int n = 20;
    Console.WriteLine(getValueOfF(n));
}
}
 
// This code is contributed by akt_mit.

<?php
//PHP implementation of the approach
// Function to return the value of F(N)
 
function getValueOfF($n)
{
 
    // Base cases
    if ($n == 1)
        return 0;
    if ($n == 2)
        return 1;
 
    $cnt = 0;
 
    // Count the number of times a number
    // if divisible by 2
    while ($n % 2 == 0)
    {
        $cnt += 1;
        $n /= 2;
    }
 
    // Return the summation
    return 2 * $cnt;
}
 
    // Driver code
    $n = 20;
    echo getValueOfF($n);
 
// This code is contributed by Tushil..
?>

<script>
    // Javascript implementation of the approach
     
    // Function to return the value of F(N)
    function getValueOfF(n)
    {
 
        // Base cases
        if (n == 1)
            return 0;
        if (n == 2)
            return 1;
 
        let cnt = 0;
 
        // Count the number of times a number
        // if divisible by 2
        while (n % 2 == 0)
        {
            cnt += 1;
            n = parseInt(n / 2, 10);
        }
 
        // Return the summation
        return 2 * cnt;
    }
     
    let n = 20;
    document.write(getValueOfF(n));
 
</script>

4

Complejidad de tiempo: O (log n), ya que estamos usando un bucle para atravesar y en cada recorrido estamos disminuyendo n por división de piso de 2, por lo tanto, el tiempo efectivo será 1+1/2+1/4+…..+ 1/2^n que es equivalente a log(n).

Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.