Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Problem
2.
Solution
3.
FAQs
4.
Key takeaways
Last Updated: Mar 27, 2024

Number of Ways to Convert 2 into N by Squaring, Adding 1, or Multiplying with 2

Author GAZAL ARORA
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Problem

Given a positive integer n, print the number of ways to convert 2 to n using any following operations:

  • Multiply the current number by 2.
  • Add 1 to the current number.
  • Square the current number.

 

Input: An integer n.

Output: Print the number of ways to convert 2 to n.
 

The questions you should ask the interviewer:

  1. What is the constraint on n?

 


Alert Ninjas:  Don’t stop now! Enroll in the Competitive Programming course today. Learn the art of writing time and space-efficient code and compete in code competitions worldwide. 


 

Examples:

1.

Input: N = 6

Output: 4

Explanation: The integer 6 can be reached from 2 by the following ways: 

  • 2 (+1) => 3 (+1) => 4  (+1) => 5 (+1) => 6.
  • 2 (+1) => 3 (*2) => 6.
  • 2 (*2) => 4 (+1) => 5 (+1) => 6.
  • 2 (^2) => 4 (+1) => 5(+1) => 6.

Therefore, the total number of ways is 4.

2.

Input: 5

Output:  3

Explanation:The integer 5 can be reached from 2 by the following ways: 

  • 2 +1 => 3 (+1) => 4  (+1) => 5.
  • 2 (*2) => 4 (+1) => 5.
  • 2 (^2) => 4 (+1) => 5.

Therefore, the total number of ways is 3.

 

Recommended: Try to solve it yourself before moving on to the solution.

Solution

 

Idea:  The idea is to use Dynamic Programming to count the number of ways required to reach N from 2. As mentioned in the question, we can do the three operations:

  • Multiply the current number by 2.
  • Add 1 to the current number.
  • Square the current number.

 

Therefore, dp[i+1], dp[i*i], dp[i*2] can be derived from dp[i].

Algorithm:

  1. Initiate a dp array where dp[i] will represent the number of ways to reach i from 2 using the operations mentioned above.
  2. The base condition will be dp[2] = 1.
  3. Iterate through the DP array from 2 to N, and use the relation that dp[i] => dp[i+1], dp[i] => dp[i*2], and dp[i] => dp[i*i].
  4. Similarly, add all the ways to calculate dp[i].
  5. Return dp[n] as the required answer.

 

C++ 

#include <bits/stdc++.h>
using namespace std;

int reachN(int n)
{
     vector<int> dp(n + 1, 0);
      // base condition.
     dp[2] = 1;

     // Iterate the array from 2 to n.
     for (int i = 2; i <= n; i++) {
         // derive dp[i+1], dp[i*i], and dp[i*2] from dp[i].
         // If i+1 is in the range.
          if (i+1 <= n) {

               dp[i+1] += dp[i];

          }
          // If i/2 is in the range.
          if (i*2 <= n) {

               dp[i*2] += dp[i];

          }
          // If i*i is in the range.
          if (i * i <= n) {
               dp[i * i] += dp[i];
          }
     }
     return dp[n];
}

int main()
{
     int n;

     cin >> n;
     cout << "Total number of ways to reach " << n <<" are: " << reachN(n);
     return 0;
}

Input: n = 6.

Output: 4

Input: n = 5.

Output: 5

Time Complexity: O(N). We used a loop from 2 to N, which will take O(N) time.

Space Complexity: O(N). Extra space is used to create the DP array.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

FAQs

  1. What is dynamic programming?
    Dynamic Programming (DP) is an algorithmic technique for solving an optimization problem by breaking it down into smaller subproblems and taking advantage of the fact that the best solution to its subproblems determines the best solution of the overall problem.
     
  2. What is the difference between recursion and dynamic programming?
    Recursion is calling the same function again and again. Dynamic Programming is a technique for resolving issues with a certain structure (optimal substructure), in which a problem is broken down into sub-problems that are similar to the original problem.

Key takeaways

 

In this article, we solved a programming question where we were given a positive integer n, and we needed to design an algorithm for counting the number of ways to convert 2 to n using the following operations:

  • Multiply the current number by 2.
  • Add 1 to the current number.
  • Square the current number.

We solved it using Dynamic Programming in O(N) time complexity and O(N) space complexity.

Coding Ninjas provides this amazing course in DP, and it covers all the important concepts and questions required to master DP. Enroll today and start coding.

Apart from that, you can use Coding Ninjas Studio to practice a wide range of DSA questions asked in lots of interviews. It will assist you in mastering efficient coding techniques, and you will also get interview experiences from people working in big companies.

Previous article
Minimum and Maximum values of an expression with * and +
Next article
Number of ways of Triangulation
Live masterclass