You are viewing a single comment's thread. Return to all comments →
Not gonna lie. Using 1d array approach was pretty faster than the 2d array approach.
from time import time GIVEN_COINS = [1, 2, 5, 10, 20, 50, 100, 200] N = len(GIVEN_COINS) MAX_AMOUNT = 10 ** 5 MOD = (10 ** 9) + 7 def using2dArray(userAmount): START = time() dp2 = [[0] * (MAX_AMOUNT + 1)] * (N + 1) for i in range(N + 1): dp2[i][0] = 1 for i in range(1, N + 1): for j in range(MAX_AMOUNT + 1): if j >= GIVEN_COINS[i-1]: dp2[i][j] = dp2[i][j-GIVEN_COINS[i-1]] + dp2[i-1][j] else: dp2[i][j] = dp2[i-1][j] answer = dp2[N][userAmount] % MOD print("Using 2D Array, Ans: {}, Time: {} seconds".format(answer, time()-START)) def using1dArray(userAmount): START = time() dp1 = [0] * (MAX_AMOUNT + 1) dp1[0] = 1 for i in range(N): for j in range(GIVEN_COINS[i], MAX_AMOUNT + 1): dp1[j] += dp1[j-GIVEN_COINS[i]] answer = dp1[userAmount] % MOD print("Using 1D Array, Ans: {}, Time: {} seconds".format(answer, time()-START)) def compare(userInput): global caseNo using2dArray(userInput) using1dArray(userInput) print("-------") compare(200) compare(1000) compare(10000) compare(100000)
Using 2D Array, Ans: 73682, Time: 0.12668895721435547 seconds Using 1D Array, Ans: 73682, Time: 0.06984210014343262 seconds ------- Using 2D Array, Ans: 321335886, Time: 0.12624073028564453 seconds Using 1D Array, Ans: 321335886, Time: 0.06981587409973145 seconds ------- Using 2D Array, Ans: 296710490, Time: 0.1266779899597168 seconds Using 1D Array, Ans: 296710490, Time: 0.06984448432922363 seconds ------- Using 2D Array, Ans: 836633026, Time: 0.12666869163513184 seconds Using 1D Array, Ans: 836633026, Time: 0.06981515884399414 seconds -------
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #31: Coin sums
You are viewing a single comment's thread. Return to all comments →
Not gonna lie. Using 1d array approach was pretty faster than the 2d array approach.