Maximize the coins using K moves
Given an integer N, the task is to maximize the coins which we can collect using K moves. In one move, we can perform one of the following operations:
- Type 1: Add N coins to our collection (N remains unchanged).
- Type 2: Add X to N, where X is the last digit of N.
Example:
Input: N = 1, K = 3
Output: 4
Explanation: The following operations are performed to maximize the number of coins collected.
- Perform Type 1 operation, N = 1 + 1 = 2
- Perform Type 1 operation N = 2 + 2 = 4
- Perform Type 2 operation, add N = 4 coins to our collection, total coins collected = 4
Input: N = 11, K = 3
Output: 33
Explanation: The following operations are performed to maximize the number of coins.
- Perform Type 2 operation, add N = 11 coins to our collection, total coins collected = 11.
- Perform Type 2 operation, add N = 11 coins to our collection, total coins collected = 22.
- Perform Type 2 operation, add N = 11 coins to our collection, total coins collected = 33.
Approach:
The solution is based on the greedy observation. So, the optimal strategy is to add bonuses first and then get the discount. This is because the more bonuses you have, the larger the discount you can get. if we keep performing operation 2, the last digit of s will cycle through the digits 2, 4, 8, 6. This leads to the formula for the answer:
ans=(s+20x)*(k-4x)
Here’s a simpler explanation of above formula:
- We start with a number s.
- Each time you perform operation 2, the last digit of s changes. If we keep performing operation 2, the last digit of s will cycle through the digits 2, 4, 8, 6.
- Each complete cycle through 2, 4, 8, 6 adds 20 to s (since 2+4+8+6 = 20).
- x represents the number of complete cycles.
- So, (s + 20x) gives us the total number of bonuses after x complete cycles.
- We can perform a total of k operations. If we use 4x operations for the cycles (since each cycle consists of 4 operations), we have (k – 4x) operations left.
- These remaining operations are used to add the total number of bonuses to the answer. So, (s + 20x) * (k – 4x) gives us the maximum possible value of the answer.
This is a parabolic equation, and its maximum can be found using the formula for the vertex of a parabola or by ternary search. The bisector of the parabola is (5k-s)/40. we can calculate the answer for each case where the last digit is 2, 4, 8, 6, and take the maximum value.
Notes:
- If the last digit of s is 5, you can perform operation 2 at most once.
- If the last digit of s is an odd number, you need to perform operation 2 once before you can enter the cycle.
Step-by-step approach:
- Declare variables lowerBound, upperBound, temp, and result.
- Initialize result to the product of numCoins and numMoves.
- Add the remainder when numCoins is divided by 10 to numCoins.
- Decrement numMoves.
- Update result with the maximum of the current result and the product of numCoins and numMoves.
- Check if numCoins is not divisible by 10.
- Calculate lowerBound as -1 and upperBound as numMoves / 4.
- Use binary search to find the optimal number of cycles.
- Update temp with the optimal number of cycles.
- Update result with the maximum of the current result and the product of (numCoins + temp * 20) and (numMoves – temp * 4).
- Add the remainder when numCoins is divided by 10 to numCoins.
- Decrement numMoves.
- Return the final value of result.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Function to return the maximum of two numbers long long max( long long a, long long b) { return a > b ? a : b; } int solve( int numCoins, int numMoves) { long long lowerBound, upperBound, temp, result; // Variable to store the remainder when the number of // coins is divided by 10 int remainder; // Initialize the result to the product of the number of // coins and moves result = numCoins * numMoves; // Add the remainder when the number of coins is divided // by 10 to the number of coins numCoins += numCoins % 10; // Decrement the number of moves numMoves--; // Update the result with the maximum of the current // result and the product of the number of coins and // moves result = max(result, numCoins * numMoves); // If the number of coins is not divisible by 10 if (numCoins % 10 != 0) { // Calculate the lower and upper bounds for the // number of cycles lowerBound = -1, upperBound = numMoves / 4; // Use binary search to find the optimal number of // cycles while (upperBound - lowerBound > 1) { temp = (lowerBound + upperBound) / 2; if ((numCoins + temp * 20) * (numMoves - temp * 4) < (numCoins + (temp + 1) * 20) * (numMoves - (temp + 1) * 4)) lowerBound = temp; else upperBound = temp; } // Calculate the optimal number of cycles temp = upperBound; // Update the result with the maximum of the current // result and the product of the number of coins // plus 20 times the number of cycles and the number // of moves minus 4 times the number of cycles result = max(result, (numCoins + temp * 20) * (numMoves - temp * 4)); // Add the remainder when the number of coins is // divided by 10 to the number of coins numCoins += numCoins % 10; // Decrement the number of moves numMoves--; } // Print the result return result; } int main() { // Variables to store the number of coins, moves, and // the result long long n = 1, k = 3; cout << solve(n, k); return 0; } |
Java
// Java code to implement the approach class GFG { static long solve( long numCoins, long numMoves) { long lowerBound, upperBound, temp, result; // Variable to store the remainder when the number // of coins is divided by 10 long remainder; // Initialize the result to the product of the // number of coins and moves result = numCoins * numMoves; // Add the remainder when the number of coins is // divided by 10 to the number of coins numCoins += numCoins % 10 ; // Decrement the number of moves numMoves--; // Update the result with the maximum of the current // result and the product of the number of coins and // moves result = Math.max(result, numCoins * numMoves); // If the number of coins is not divisible by 10 if (numCoins % 10 != 0 ) { // Calculate the lower and upper bounds for the // number of cycles lowerBound = - 1 ; upperBound = numMoves / 4 ; // Use binary search to find the optimal number // of cycles while (upperBound - lowerBound > 1 ) { temp = (lowerBound + upperBound) / 2 ; if ((numCoins + temp * 20 ) * (numMoves - temp * 4 ) < (numCoins + (temp + 1 ) * 20 ) * (numMoves - (temp + 1 ) * 4 )) lowerBound = temp; else upperBound = temp; } // Calculate the optimal number of cycles temp = upperBound; // Update the result with the maximum of the // current result and the product of the number // of coins plus 20 times the number of cycles // and the number of moves minus 4 times the // number of cycles result = Math.max(result, (numCoins + temp * 20 ) * (numMoves - temp * 4 )); // Add the remainder when the number of coins is // divided by 10 to the number of coins numCoins += numCoins % 10 ; // Decrement the number of moves numMoves--; } // Print the result return result; } public static void main(String[] args) { // Variables to store the number of coins, moves, // and the result long n = 1 , k = 3 ; System.out.println(solve(n, k)); } } // This code is contributed by ragul21 |
Python3
def solve(numCoins, numMoves): # Initialize the result to the product of the number of coins and moves result = numCoins * numMoves # Add the remainder when the number of coins is divided by 10 to the number of coins numCoins + = numCoins % 10 # Decrement the number of moves numMoves - = 1 # Update the result with the maximum of the current result and the product of the number of coins and moves result = max (result, numCoins * numMoves) # If the number of coins is not divisible by 10 if numCoins % 10 ! = 0 : # Calculate the lower and upper bounds for the number of cycles lowerBound = - 1 upperBound = numMoves / / 4 # Use binary search to find the optimal number of cycles while upperBound - lowerBound > 1 : temp = (lowerBound + upperBound) / / 2 if (numCoins + temp * 20 ) * (numMoves - temp * 4 ) < (numCoins + (temp + 1 ) * 20 ) * (numMoves - (temp + 1 ) * 4 ): lowerBound = temp else : upperBound = temp # Calculate the optimal number of cycles temp = upperBound # Update the result with the maximum of the current result and the product of the number # of coins plus 20 times the number of cycles and the number of moves minus 4 times the number of cycles result = max (result, (numCoins + temp * 20 ) * (numMoves - temp * 4 )) # Add the remainder when the number of coins is divided by 10 to the number of coins numCoins + = numCoins % 10 # Decrement the number of moves numMoves - = 1 # Print the result return result # Variables to store the number of coins, moves, and the result n, k = 1 , 3 print (solve(n, k)) # This code is contributed by rohit singh |
C#
using System; public class Program { // Function to return the maximum of two numbers public static long Max( long a, long b) { return a > b ? a : b; } public static int Solve( int numCoins, int numMoves) { long lowerBound, upperBound, temp, result; // Initialize the result to the product of the number of // coins and moves result = numCoins * numMoves; // Add the remainder when the number of coins is divided // by 10 to the number of coins numCoins += numCoins % 10; // Decrement the number of moves numMoves--; // Update the result with the maximum of the current // result and the product of the number of coins and // moves result = Max(result, numCoins * numMoves); // If the number of coins is not divisible by 10 if (numCoins % 10 != 0) { // Calculate the lower and upper bounds for the // number of cycles lowerBound = -1; upperBound = numMoves / 4; // Use binary search to find the optimal number of // cycles while (upperBound - lowerBound > 1) { temp = (lowerBound + upperBound) / 2; if ((numCoins + temp * 20) * (numMoves - temp * 4) < (numCoins + (temp + 1) * 20) * (numMoves - (temp + 1) * 4)) lowerBound = temp; else upperBound = temp; } // Calculate the optimal number of cycles temp = upperBound; // Update the result with the maximum of the current // result and the product of the number of coins // plus 20 times the number of cycles and the number // of moves minus 4 times the number of cycles result = Max(result, (numCoins + temp * 20) * (numMoves - temp * 4)); // Add the remainder when the number of coins is // divided by 10 to the number of coins numCoins += numCoins % 10; // Decrement the number of moves numMoves--; } // Return the result return ( int )result; } public static void Main() { // Variables to store the number of coins, moves, and // the result long n = 1, k = 3; Console.WriteLine(Solve(( int )n, ( int )k)); } } |
Javascript
// JavaScript Implementation // Function to solve the problem function solve(numCoins, numMoves) { // Initialize variables for bounds, temporary values, and result let lowerBound, upperBound, temp, result; // Variable to store the remainder when the number of coins is divided by 10 let remainder; // Initialize result with the product of numCoins and numMoves result = numCoins * numMoves; // Adjust numCoins by adding its remainder when divided by 10 numCoins += numCoins % 10; // Decrement numMoves numMoves--; // Update result with the maximum of the current result and the product of numCoins and numMoves result = Math.max(result, numCoins * numMoves); // Check if numCoins is not divisible by 10 if (numCoins % 10 !== 0) { // Initialize lowerBound to -1 and upperBound to the floor of numMoves divided by 4 lowerBound = -1; upperBound = Math.floor(numMoves / 4); // Use binary search to find the optimal number of cycles while (upperBound - lowerBound > 1) { temp = Math.floor((lowerBound + upperBound) / 2); if ((numCoins + temp * 20) * (numMoves - temp * 4) < (numCoins + (temp + 1) * 20) * (numMoves - (temp + 1) * 4)) { lowerBound = temp; } else { upperBound = temp; } } // Calculate the optimal number of cycles temp = upperBound; // Update result with the maximum of the current result and the product of numCoins plus 20 times the number of cycles and the number of moves minus 4 times the number of cycles result = Math.max(result, (numCoins + temp * 20) * (numMoves - temp * 4)); // Add the remainder when the number of coins is divided by 10 to numCoins numCoins += numCoins % 10; // Decrement numMoves numMoves--; } // Return the result return result; } // Main function const n = 1; const k = 3; // Output the result of calling the solve function with n and k as arguments console.log(solve(n, k)); // This code is contributed by Tapesh(tapeshdu420) |
4
Time Complexity: O(log k) due to the binary search.
Auxiliary Space: O(1)