Exchanging coins dp timelimit

#1

code:

EXCHANGING COINS
Tughlaq introduces a strange monetary system. He introduces copper coins and each coin has a number written on it. A coin n can be exchanged in a bank into three coins: n/2, n/3 and n/4. A coin can also be sold for gold. One can get as much grams of gold as the number written on the coin. You have one copper coin. What is the maximum weight of gold one can get from it?

Input Format:
The input file contains a single integer n, the number on the coin.

Constraints:
0 <= n <= 1 000 000 000

Output Format
Print the maximum weight of gold you can get.

Sample Input
12
Sample Output
13

#2

Hey @poorva2145
You’re getting a tle because an array/vector can have a maximum size of 1000000, so you can’t make dp table of size > 1000000. There’s a way to tackle this, by making dp table of size 1000000 only, and handling bigger numbers using certain recursion, refer to the following code:
(https://ide.codingblocks.com/s/168137)

1 Like