Given integer N and values P and Q, The task is to calculate the minimum number of powers of P and Q required to generate N.
Note: The 0th power of the values is also considered.
Examples:
Input: N = 15, P = 2, Q = 3
Output: 3
Explanation: We can make 15 by using (8, 4, 3) or (9, 3, 3). Both take 3 numbers.Input: N = 19, P = 4, Q = 3
Output: 2
Explanation: In the second case, we can make 19 by using (16, 3) which is 2 numbers.
Approach: Recursion (Memoization)
The Basic idea is to use memoization approach for this problem, simply we’ll check ways to reach or to generate N by considering both P and Q powers by making recursive calls.
Pseudo Code:
To check the powers being used in recursive relation.
‘long long int a=1;
ans = 1e9; // to store potential answer
if(power = 1){
return n;
}
while(n-a >= 0)
{
ans = min(ans, dp[n-a]);
a = a*power;
}
return ans+1;
Follow the steps mentioned below to implement the idea:
- Initialize a dp[] array of size N+1 and initialize it with 1e9.
- Set, the base cases, dp[0] = 0 and dp[1] = 1.
- Traverse through 2 to N and find the ways with powers.
- Way1 by considering the power of P.
- Way2 by considering the power of Q.
- Consider dp[i] = min(way1, way2).
- After traversing return dp[N].
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to check minimum steps for// a particular power for nint check(int n, int power, vector<int>& dp){ // Initialize the variables long long int a = 1; int ans = 1e9; // Edge Case if (power == 1) return n; // Until N hits 0 while (n - a >= 0) { ans = min(ans, dp[n - a]); a = a * power; } return ans + 1;}// Function to find minimum number// of stepsint moves(int n, int p, int q){ // Initialize a dp array vector<int> dp(n + 1, 1e9); // Base Case dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; ++i) { int way1 = check(i, p, dp); int way2 = check(i, q, dp); dp[i] = min(way1, way2); } // Return dp[] as answer return dp[n];}// Driver Codeint main(){ int N = 15, P = 2, Q = 3; // Function call cout << moves(N, P, Q) << endl; return 0;} |
Java
// Java code to implement the approachimport java.util.*;public class GFG { // Function to check minimum steps for // a particular power for n public static int check(int n, int power, int dp[]) { // Initialize the variables long a = 1; int ans = Integer.MAX_VALUE; // Edge Case if (power == 1) return n; // Until N hits 0 while (n - a >= 0) { ans = Math.min(ans, dp[n - (int)a]); a = a * power; } return ans + 1; } // Function to find minimum number // of steps public static int moves(int n, int p, int q) { // Initialize a dp array int dp[] = new int[n + 1]; for (int i = 0; i < n + 1; i++) { dp[i] = Integer.MAX_VALUE; } // Base Case dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; ++i) { int way1 = check(i, p, dp); int way2 = check(i, q, dp); dp[i] = Math.min(way1, way2); } // Return dp[] as answer return dp[n]; } // Driver Code public static void main(String args[]) { int N = 15, P = 2, Q = 3; // Function call System.out.println(moves(N, P, Q)); }}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python code to implement the approach# Function to check minimum steps for a particular power of ndef check(n, power, dp): # Initialize the variables a = 1 ans = float("inf") # Edge case if(power == 1): return n # Until N hits 0 while(n-a >= 0): ans = min(ans, dp[n-a]) a = a * power return ans + 1# Function to find minimum number of stepsdef moves(n, p, q): # Initialize a dp array dp = [float("inf")]*(n+1) # Base case dp[0] = 0 dp[1] = 1 for i in range(2, n+1): way1 = check(i, p, dp) way2 = check(i, q, dp) dp[i] = min(way1, way2) # Return dp[] as answer return dp[n]N, P, Q = 15, 2, 3# Function Callprint(moves(N, P, Q))# This code is contributed by lokeshmvs21. |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;class GFG { // Function to check minimum steps for // a particular power for n public static int check(int n, int power, int[] dp) { // Initialize the variables long a = 1; int ans = int.MaxValue; // Edge Case if (power == 1) return n; // Until N hits 0 while (n - a >= 0) { ans = Math.Min(ans, dp[n - (int)a]); a = a * power; } return ans + 1; } // Function to find minimum number // of steps public static int moves(int n, int p, int q) { // Initialize a dp array int[] dp = new int[n + 1]; for (int i = 0; i < n + 1; i++) { dp[i] = int.MaxValue; } // Base Case dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; ++i) { int way1 = check(i, p, dp); int way2 = check(i, q, dp); dp[i] = Math.Min(way1, way2); } // Return dp[] as answer return dp[n]; } // Driver Code public static void Main(String[] args) { int N = 15, P = 2, Q = 3; // Function call Console.WriteLine(moves(N, P, Q)); }}// This code is contributed by Tapesh(tapeshdua420) |
Javascript
// Javascript code to implement the approach// Function to check minimum steps for a particular power of nfunction check(n, power, dp) { // Initialize the variables var a = 1; var ans = Number.MAX_VALUE; // Edge case if (power == 1) { return n; } // Until N hits 0 while (n - a >= 0) { ans = Math.min(ans, dp[n - a]); a = a * power; } return ans + 1;}// Function to find minimum number of stepsfunction moves(n, p, q) { // Initialize a dp array var dp = new Array(n + 1).fill(Number.MAX_VALUE); // Base case dp[0] = 0; dp[1] = 1; for (var i = 2; i <= n; i++) { var way1 = check(i, p, dp); var way2 = check(i, q, dp); dp[i] = Math.min(way1, way2); } // Return dp[] as answer return dp[n];}var N = 15, P = 2, Q = 3;// Function Callconsole.log(moves(N, P, Q));// This code is contributed by Tapesh(tapeshdua420) |
Output
3
Time Complexity: O(N * log N)
Auxiliary Space: O(N )
Related Articles:
- Introduction to Dynamic Programming – Data Structures and Algorithm Tutorials
- Write a program to calculate pow(x, 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!
