Given integers N, P and Q where N denotes the destination position. The task is to move from position 0 to position N with minimum cost possible and print the calculated cost. All valid movements are:
- From position X you can go to position X + 1 with a cost of P
- Or, you can go to the position 2 * X with a cost of Q
Examples:
Input: N = 1, P = 3, Q = 4
Output: 3
Move from position 0 to 1st position with cost = 3.
Input: N = 9, P = 5, Q = 1
Output: 13
Move from position 0 to 1st position with cost = 5,
then 1st to 2nd with cost = 1,
then 2nd to 4th with cost = 1,
then 4th to 8th with cost = 1,
finally 8th to 9th with cost = 5.
Total cost = 5 + 1 + 1 + 1 + 5 = 13.
Approach: Instead of going from beginning to destination we can start moving from the destination to initial position and keep track of the cost of jumps.
- If N is odd then the only valid move that could lead us here is N-1 to N with a cost of P.
- If N is even then we calculate cost of going from N to N/2 position with both the moves and take the minimum of them.
- When N equals 0, we return our total calculated cost.
Below is the implementation of above approach:
C++
// CPP implementation of above approach#include <bits/stdc++.h>using namespace std;// Function to return minimum// cost to reach destinationint minCost(int N, int P, int Q){ // Initialize cost to 0 int cost = 0; // going backwards until we // reach initial position while (N > 0) { if (N & 1) { cost += P; N--; } else { int temp = N / 2; // if 2*X jump is // better than X+1 if (temp * P > Q) cost += Q; // if X+1 jump is better else cost += P * temp; N /= 2; } } // return cost return cost;}// Driver programint main(){ int N = 9, P = 5, Q = 1; cout << minCost(N, P, Q); return 0;} |
Java
// Java implementation of above approachclass GFG{// Function to return minimum// cost to reach destinationstatic int minCost(int N, int P, int Q){ // Initialize cost to 0 int cost = 0; // going backwards until we // reach initial position while (N > 0) { if ((N & 1)>0) { cost += P; N--; } else { int temp = N / 2; // if 2*X jump is // better than X+1 if (temp * P > Q) cost += Q; // if X+1 jump is better else cost += P * temp; N /= 2; } } // return cost return cost;}// Driver programpublic static void main(String[] args){ int N = 9, P = 5, Q = 1; System.out.println(minCost(N, P, Q));}}// This code is contributed by mits |
Python3
# Python implementation of above approach # Function to return minimum # cost to reach destinationdef minCost(N,P,Q): # Initialize cost to 0 cost = 0 # going backwards until we # reach initial position while (N > 0): if (N & 1): cost += P N-=1 else: temp = N // 2; # if 2*X jump is # better than X+1 if (temp * P > Q): cost += Q # if X+1 jump is better else: cost += P * temp N //= 2 return cost # Driver program N = 9P = 5Q = 1print(minCost(N, P, Q))#this code is improved by sahilshelangia |
C#
// C# implementation of above approachclass GFG{// Function to return minimum// cost to reach destinationstatic int minCost(int N, int P, int Q){ // Initialize cost to 0 int cost = 0; // going backwards until we // reach initial position while (N > 0) { if ((N & 1) > 0) { cost += P; N--; } else { int temp = N / 2; // if 2*X jump is // better than X+1 if (temp * P > Q) cost += Q; // if X+1 jump is better else cost += P * temp; N /= 2; } } // return cost return cost;}// Driver Codestatic void Main(){ int N = 9, P = 5, Q = 1; System.Console.WriteLine(minCost(N, P, Q));}}// This code is contributed by mits |
PHP
<?php// PHP implementation of above approach// Function to return minimum// cost to reach destinationfunction minCost($N, $P, $Q){ // Initialize cost to 0 $cost = 0; // going backwards until we // reach initial position while ($N > 0) { if ($N & 1) { $cost += $P; $N--; } else { $temp = $N / 2; // if 2*X jump is // better than X+1 if ($temp * $P > $Q) $cost += $Q; // if X+1 jump is better else $cost += $P * $temp; $N /= 2; } } // return cost return $cost;}// Driver Code$N = 9; $P = 5; $Q = 1;echo minCost($N, $P, $Q);// This code is contributed // by Akanksha Rai?> |
Javascript
<script>//Javascript implementation of above approach// Function to return minimum// cost to reach destinationfunction minCost( N, P, Q){ // Initialize cost to 0 var cost = 0; // going backwards until we // reach initial position while (N > 0) { if (N & 1) { cost += P; N--; } else { var temp =parseInt( N / 2); // if 2*X jump is // better than X+1 if (temp * P > Q) cost += Q; // if X+1 jump is better else cost += P * temp; N = parseInt(N / 2); } } // return cost return cost;}var N = 9, P = 5, Q = 1;document.write( minCost(N, P, Q));//This code is contributed by SoumikMondal</script> |
Output:
13
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
