Dado un número positivo N , la tarea es encontrar el número de formas de llegar a N a partir de 2, donde cada operación se puede realizar una de las siguientes:
- Suma 1 al número actual.
- Multiplica el número actual por 2.
- Eleva al cuadrado el número actual.
Ejemplo:
Entrada: N = 5
Salida: 3
Explicación: Se puede llegar al entero5 de las siguientes maneras:
- 2 (+1) => 3 (+1) => 4 (+1) => 5
- 2 (*2) => 4 (+1) => 5
- 2 (^2) => 4 (+1) => 5
Por lo tanto, el número de formas de llegar a 5 desde 2 es 3.
Entrada: N = 9
Salida: 8
Enfoque: el problema dado se puede resolver de manera eficiente mediante el uso de programación dinámica . La idea es usar una array DP para calcular la cantidad de formas requeridas para llegar a N desde 2. Iterar la array Dp de 2 a N y después de cada iteración realizar las operaciones mencionadas para calcular la cantidad de formas requeridas para llegar a N , es decir, Dp [i] => Dp[i+1] , Dp[i] => Dp[2 * i] y Dp[i] => Dp[i * i] . Por lo tanto, agregue el número de formas de llegar a Dp[i] en los tres estados mencionados anteriormente. El valor almacenado en Dp[N] es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate
// number of ways required
// to reach N from 2
int waysToReach(int N)
{
// Initialize a DP array
vector<int> Dp(N + 1, 0);
// Initialize a DP[2] by 1
Dp[2] = 1;
// Iterate the array from 2 to N
for (int i = 2; i <= N; i++) {
// If i+1 is not out of bounds
if (i + 1 <= N) {
// Add the number of ways
Dp[i + 1] += Dp[i];
}
// If i*2 is not out of bounds
if (i * 2 <= N) {
// Add the number of ways
Dp[i * 2] += Dp[i];
}
// If i*i is not out of bounds
if (i * i <= N) {
// Add the number of ways
Dp[i * i] += Dp[i];
}
}
// Return the answer
return Dp[N];
}
// Driver code
int main()
{
int N = 5;
cout << waysToReach(N);
return 0;
}
// This code is contributed by rakeshsahni
Java
// Java implementation for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to calculate
// number of ways required
// to reach N from 2
public static int waysToReach(int N)
{
// Initialize a DP array
int[] Dp = new int[N + 1];
// Initialize a DP[2] by 1
Dp[2] = 1;
// Iterate the array from 2 to N
for (int i = 2; i <= N; i++) {
// If i+1 is not out of bounds
if (i + 1 <= N) {
// Add the number of ways
Dp[i + 1] += Dp[i];
}
// If i*2 is not out of bounds
if (i * 2 <= N) {
// Add the number of ways
Dp[i * 2] += Dp[i];
}
// If i*i is not out of bounds
if (i * i <= N) {
// Add the number of ways
Dp[i * i] += Dp[i];
}
}
// Return the answer
return Dp[N];
}
// Driver code
public static void main(String[] args)
{
int N = 5;
System.out.println(waysToReach(N));
}
}
Python3
# Python Program to implement # the above approach # Function to calculate # number of ways required # to reach N from 2 def waysToReach(N): # Initialize a DP array Dp = [0] * (N + 1) # Initialize a DP[2] by 1 Dp[2] = 1 # Iterate the array from 2 to N for i in range(2, N + 1): # If i+1 is not out of bounds if (i + 1 <= N): # Add the number of ways Dp[i + 1] += Dp[i] # If i*2 is not out of bounds if (i * 2 <= N): # Add the number of ways Dp[i * 2] += Dp[i] # If i*i is not out of bounds if (i * i <= N): # Add the number of ways Dp[i * i] += Dp[i] # Return the answer return Dp[N] # Driver code N = 5 print(waysToReach(N)) # This code is contributed by gfgking
C#
// C# program for above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
// Function to calculate
// number of ways required
// to reach N from 2
static int waysToReach(int N)
{
// Initialize a DP array
int []Dp = new int[N+1];
for(int i = 0; i < N+1; i++) {
Dp[i] = 0;
}
// Initialize a DP[2] by 1
Dp[2] = 1;
// Iterate the array from 2 to N
for (int i = 2; i <= N; i++) {
// If i+1 is not out of bounds
if (i + 1 <= N) {
// Add the number of ways
Dp[i + 1] += Dp[i];
}
// If i*2 is not out of bounds
if (i * 2 <= N) {
// Add the number of ways
Dp[i * 2] += Dp[i];
}
// If i*i is not out of bounds
if (i * i <= N) {
// Add the number of ways
Dp[i * i] += Dp[i];
}
}
// Return the answer
return Dp[N];
}
// Driver Code
public static void Main()
{
int N = 5;
Console.Write(waysToReach(N));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to calculate
// number of ways required
// to reach N from 2
function waysToReach(N) {
// Initialize a DP array
let Dp = new Array(N + 1).fill(0);
// Initialize a DP[2] by 1
Dp[2] = 1;
// Iterate the array from 2 to N
for (let i = 2; i <= N; i++) {
// If i+1 is not out of bounds
if (i + 1 <= N) {
// Add the number of ways
Dp[i + 1] += Dp[i];
}
// If i*2 is not out of bounds
if (i * 2 <= N) {
// Add the number of ways
Dp[i * 2] += Dp[i];
}
// If i*i is not out of bounds
if (i * i <= N) {
// Add the number of ways
Dp[i * i] += Dp[i];
}
}
// Return the answer
return Dp[N];
}
// Driver code
let N = 5;
document.write(waysToReach(N));
// This code is contributed by Potta Lokesh
</script>
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ankansadhukhan2003 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA