Given a positive number N, the task is to find the number of ways to reach N from 2 wherein each operation one of the following can be performed:
- Add 1 to the current number.
- Multiply the current number by 2.
- Square the current number.
Example:
Input: N = 5
Output: 3
Explanation: The integer 5 can be reached by the following ways:
- 2 (+1) => 3 (+1) => 4 (+1) => 5
- 2 (*2) => 4 (+1) => 5
- 2 (^2) => 4 (+1) => 5
Therefore, the number of ways of reaching 5 from 2 are 3.
Input: N = 9
Output: 8
Approach: The given problem can be solved efficiently by using dynamic programming. The idea is to use a DP array to calculate the number of ways required to reach N from 2. Iterate the array Dp from 2 to N and after each iteration perform the mentioned operations to calculate the number of ways required to reach N i.e, Dp[i] => Dp[i+1], Dp[i] => Dp[2 * i], and Dp[i] => Dp[i * i]. Therefore, add the number of ways to reach Dp[i] in all the three states mentioned above. The value stored at Dp[N] is the required answer.
Below is the implementation of the above approach:
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 2int 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 codeint main(){ int N = 5; cout << waysToReach(N); return 0;} // This code is contributed by rakeshsahni |
Java
// Java implementation for the above approachimport 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 2def 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 codeN = 5print(waysToReach(N))# This code is contributed by gfgking |
C#
// C# program for above approachusing System;using System.Collections;using System.Collections.Generic;class GFG{// Function to calculate// number of ways required// to reach N from 2static 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 Codepublic 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> |
Output
3
Time Complexity: O(N)
Auxiliary Space: O(N)
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
