[Challenge] Change Please

challenge

#1

Code Challenge #16: July 26, 2017

Every week, we feature the type of brain-teasing question that might be asked in a full-stack developer's job interview at places such as Google and Facebook.

This week's challenge was reported to have been asked in interviews at Google:


The Challenge

You're building an ATM and want to know how many ways you can "break" a given amount of money into cash or change.
To do so, write a function, changeOptions, that when fed an amount of money n and a list of values S = { S1, S2, .. , Sm} (representing the possible coin or note denominations), will return the number of all the possible ways in which one can break down n into change.

  • Function Name: changeOptions
  • Input: n, an integer ≥0 and an integer array S which is the list of all denominations.
  • Output: an integer, the number of all of the possible combinations of coins and notes that add up to n
  • Example: changeOptions(5, [1, 2, 5, 10, .., 50000]) => 4
    • Where the amount is 5¢ (n=5) and the denominations are S = [1, 2, 5, 10, .., 50000], the possible combinations of coins and notes that add up to 5 are 1+1+1+1+1, 1+1+1+2, 1+2+2, 5, so your function would return 4.
    • The order of the coins and notes doesn't matter – 2¢+1¢+2¢ is the same amount of money as 2¢+2¢+1¢.
  • n and S both represent the number of cents – for example do not use €2.50 as an input, use 250 instead.
  • use as your sample problem n = 26730 and S = [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000]

Hard Difficulty

Write changeOptions as efficiently as possible.

Find out more about hard challenges and Big O

Reply to this thread with a link to your code on repl.it and paste your properly formatted code to participate! Don't just submit your code, remember to explain your solution, too! If you want to be considered as the winner, your function must have the correct name and provide output in the format specified above, you also need to abide by our other simple rules.

As always solutions using imports to do all the heavy lifting such as itertools will not be considered for the winner.


The fine print:

Click the links to find out more about:


Essential Information on Code Challenges
#2

Can we assume the list of values is already sorted from lowest to highest value? Or should we sort it too?


#3

This is 3rd method, it take forever to run big number
https://repl.it/JjZ1/12

Optimizing it further since last edit.

def changeOptions(n,arr):
  ram=[ [n,0] ]
  ret=0
  while ram:
    x0,x1=ram.pop()
    for i in arr:
      if i < x1:
        pass
      elif i == x0:
        ret+=1
      elif i < x0:
        ram.append([x0-i,i]);
  return ret
  
print changeOptions(200,[1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000])

Tried method below, but doesn’t work well
1st : Create a function that always break a number into 2 number, and then recursive loop, doesn’t work
2nd: Loop to break n into 1,2,3…n combination item, work, but take very long time to solve big number


#4

Here's my attempt using Python 3: https://repl.it/Jj97/5
The logic behind my attempt goes like this:
-Loop through the values in 'S', from the highest to the lowest
-If 'value' is lower or equal than 'n', subtract 'value' to 'n', and repeat this until 'n' = 0
-After finishing the current change combination, repeat this process, starting at the second highest value from the previous sub list
-Example using the sample problem: n = 26730, so the first value from 'S' to be used for the first combination would be 20000; then the second combination will start with the next value, in this case 10000, and so on, until only 1 is used (the lowest value in 'S'; this is the last combination possible)

def changeOptions(n, S):
    sub_S = [] #a sub list of the orignal 'S' list; which will only hold the values relevant to the calculations
    n_ = n #create a copy of 'n', the original ammount of money; 'n_' will only be used during calculations
    sub_count = 0 #this variable is incremented each time a combination is finished (not counting the very first combination); it is used to decide the length of 'sub_S'
    comb_count = 0 #a counter for how many change combinations have been made; the value returned at the end of the function
    
    #loop through the values in 'S', from the highest to the lowest value (this means the list is reversed in the loop)
    for value in S[::-1]:
        #if 'value' is lower than 'n', then subtract 'value' from 'n' as many times as possible; this way the current 'value' will never have to be tested again
        if value <= n_: 
            #if 'sub_S' is still an empty list, then 'sub_S' is assigned as a sub list of 'S', containing only the relevant values to 'n'; will contain the highest value in 'S' that is lower or equal than 'n', and all the other values lower than that
            if sub_S == []:
                highest = S.index(value) #this variable is later used to automatize the creation of the other 'sub_S'
                sub_S = S[:highest][::-1]
            subtract = int(n_/value)
            n_ -= subtract * value
            
    n_ = n #reset 'n_' to the value of the initial 'n'
    comb_count += 1 #one combination has been created, so increment 'comb_count' by one

    #now to get the rest of the combinations, use the sub list 'sub_S'
    #to make the process of creating the following sub lists automatic, the 'sub_count' variable comes into play: 
    #each time a new sub list is created, its highest value will be the second highest value from the previous sub list, and so on, until 'sub_S' is empty ('highest - sub_count < 0')
    while (highest - sub_count) >= 0:
        for value in sub_S:
            if value <= n_: #if value is lower than n, then subtract value from n as many times as possible, this way the current value will never have to be tested again
                subtract = int(n_/value)
                n_ -= subtract * value
        #reset and increment the necessary variables
        n_ = n
        sub_count += 1
        sub_S = S[:(highest - sub_count)][::-1] #this is used to create the new sublist
        comb_count += 1

    return comb_count

print('changeOptions(5, [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000]) =>', changeOptions(5, [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000]))
print('changeOptions(26730, [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000]) =>', changeOptions(26730, [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000]))

#5

A post was split to a new topic: Classic dynamic programming question


#6

Hard difficulty in Python, using Dynamic Programming and Memoization to handle the overlapping sub-problems.

https://repl.it/JkYC/1

def changeOptions(n, S):
  # Input validation
    if n < 0 or n%1 != 0:
      return 0
  
    # Initialize list for memoization
    table = [0 for x in range(n+1)]
    
    # Initialize base case (n = 0; 1 solution, return no coins)
    table[0] = 1
    
    # Loop over coins
    for i in range(0,len(S)):
        # Loop over values of n. Number of combinations involving adding the
        # current coin is equal to number of previous combinations for (n-Sj)
        for j in range(S[i],n+1):
            table[j] += table[j-S[i]]
        
    return table[n]

S = [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000]
print changeOptions(5, S)
print changeOptions(26730, S)

#8

I’ve written a solution using Python 3. The code can be found here: https://repl.it/JlF8/13
First, the script sorts S numerically from highest to lowest (regardless of the order in which the cash demoninations are entered). I immediately discard any demoninations that are greater than the total amount of money (i.e. n).
The script loops through remaining values of S. For each value of S, it calculates the difference between that denomination and the total amount (n). Any denominations greater than the difference are temporarily discarded. The script then calculates all of the possible combinations of the remaining cash denominations. Each combination is tested to see if it matches the desired total. (Note that the number of combinations is first reduced to only calculate combinations in which the number of any given denomination does not exceed the difference–this could probably be reduced further in the future by applying more sophisticated rules).
Before coming to this solution, I also tried a vectorised solution in which all possible combinations were calculated (here: https://repl.it/JlEC/4)–it deals well with small n but overloads memory with large n.

‘’'
import numpy as np
def changeOptions(n, S):
# Sort S from highest to lowest
S.sort(reverse=True)
S = np.array(S)

# Values in S greater than n can be discarded immediately
S = S[S <= float(n)]

# Initialise variable to count the number of combinations that give 
# desired value of n
countCombs = 0;

# Loop through
for (idx, currentS) in enumerate(S):
    # Discard values greater than current S (will have already been computed)
    relevantS = S[idx:]
    
    # Calculate the remainder after subtracting currentS from n
    rem = n - currentS
    
    if (rem==0):
        # If there's no remainder after taking one coin, this will be one 
        # combination
        countCombs += 1
        
    else:        
        # If there is a remainder after taking out one coin, we want to determine
        # the different ways in which the smaller coins can be combined to make
        # up the remainder.
        
        # Limit to values that are less than the difference between n and currentS
        relevantS = relevantS[relevantS <= rem]
        
        # Find the maximum number of coins of each denomination that go into  
        # the difference
        maxVals = np.floor((rem / relevantS)) + 1
        
        # Find number of possible combinations of relevantS
        nCombs = int(np.prod(maxVals))
    
        # Initialise weights of each coin type
        weights = list(map(int, np.zeros(len(relevantS))))
        
        # Loop through possible combinations of remaining coins to see which 
        # combinations total to n 
        for c in range(nCombs):
                
            tmp = 1
            for idx, weight in enumerate(weights):
                weights[idx] = np.remainder(np.floor(c/tmp), maxVals[idx])
                tmp = tmp * maxVals[idx]
                
            if ((np.sum(weights * relevantS) + currentS) == n):
                countCombs += 1
            
# Find the number of combinations that equal the desired total
return countCombs

‘’’


#9

https://repl.it/JkeP/12

def changeOptions(n, S):
if n < 0: #
return 0 #

myresult = [0 for b in range(n+1)] # Function calls or tabling
myresult[0] = 1 #Values for n. If 0 then no money :p
denom = len(S) #Denomination variable

for denomR in range(0,denom): #loops for Denominations
 #Loops to find the possible Combinations from thevalue of n. Total of the withdrawal amount from the possible combinations
    for totalcombi in range(S[denomR],n+1):
        myresult[totalcombi]+=\
        myresult[totalcombi-S[denomR]]    

return myresult[n]

S = 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000
W = 10

print(S,’ Available denomniation’)
print(‘Withdrawal amount:’, W)
print('Number of Possible Combinations: ', changeOptions(W,S))


#10

Here’s a solution in Javascript: https://repl.it/JmAe/0

This is pretty much a brute force effort to find all the combinations. As such it takes a long time to run for large values.

let compareNumbersDecending = function(a, b) {
  return b - a;
}
let compareNumbers = function(a, b) {
  return a - b;
}

let denominations = [
  1,
  2,
  5,
  10,
  20,
  50,
  100,
  200,
  500,
  1000,
  2000,
  5000,
  10000,
  20000,
  50000
];

let changeOptions = function(ammount, denominations) {
  // Can't use a denomination bigger than the ammount, so filtering out.
  denominations = denominations.filter(v => v <= ammount);
  // Want to start with the largest denomination first.
  denominations = denominations.sort(compareNumbersDecending);

  let denomMap = new Map();
  denominations.forEach(v => {
    denomMap.set(v, Math.floor(ammount / v));
  });

  let combinationCount = 0;
  let combinations = {};
  let advance = true;
  while (advance) {
    advance = false;
    let testAmmount = ammount;
    let change = [];
    let denominationsUsed = [];
    for (let [key,
      quantity]of denomMap) {
      let times = Math.floor(testAmmount / key);
      times = (times < quantity)
        ? times
        : quantity;
      if (times > 0) {
        for (let i = 0; i < times; i++) {
          change.push(key);
        }
        denominationsUsed.push(key);
      }
      testAmmount -= (key * times);
    }
    if (testAmmount == 0) {
      combinations[change.join(',')] = 1;
      advance = true;
    }
    if (change[0] == 1) {
      advance = false;
    } else {
      // Need to vary which denomination gets reduced.
      let index = denominationsUsed.length - 2;
      index = (index < 0)
        ? 0
        : index;
      let quantity = denomMap.get(denominationsUsed[index]);
      denomMap.set(denominationsUsed[index], quantity - 1);
      if (quantity == 1) {
        let resetIndex = denominations.indexOf(denominationsUsed[index]) + 1;
        for (let i = resetIndex; i < denominations.length; i++) {
          denomMap.set(denominations[i], Math.floor(ammount / denominations[i]));
        }
        combinationCount += Object.keys(combinations).length;
        combinations = {};
      }
    }
  }
  return combinationCount;
}

result = changeOptions(26730, denominations);
console.log(result);

#12

Link to code here

def changeOptions(n,S):
  
  #set up values to iterate over 
  nums = [0] * (n+1)
  
  #first value is 1, or otherwise specified in "S"
  nums[0] = 1 
  
  #only iterate over denominations in "S" array 
  for denomination in S: 
    
    #iterate from denomination to number of elements in n 
    for i in range(denomination,n+1): 
      
      #find the number of possibilities for each increment 
      nums[i] += nums[i-denomination]
  
  #return integar value of the number of nums      
  return int(nums[n])  

n = 26730
S = [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000]
 
print changeOptions(n,S)



#13

Link to submission: https://repl.it/JoLv/0
My submission is coded in Python 2.7 using a mobile iOS interpreter.
The function is recursive to minimise the length of the function by lines. The function iterates through each coin value from the given array S. If the coin is too large for the value requested (> int n), the loop terminates and returns the variable solutions which counts how many combinations of change have been found. If the coin of a given iteration is equal to the required value, solutions is increased by 1 and the loop is also terminated (because the next coin is guaranteed to be larger than n). If neither of those solutions are true (lines 4 and 6), the function calls ‘itself’ - it recurs. However, each new layer of recursion is called with the n parameter equal to the n variable minus the coin variable in that iteration of the loop. To prevent duplicates, combinations are only formed in ascending order of values. This means that if the first layer of the function calls another layer with a coin value at 1, the next layer can only use values equal to or above 1. The enumerate generator of the loop is used to keep track of the index of the coin during each iteration. The index variable allows the next layer to only be passed the values in S that are upwards (or equal to) that of the coin value.

def changeOptions(n,S):
    solutions = 0
    for index,coin in enumerate(S):
        if coin > n:
            break
        elif coin == n:
            solutions += 1
            break
        else:
            solutions += changeOptions(n-coin,S[index:])
    return solutions
n = 26730
S = [1,2,5,10,20,50,100,200,500,1000,2000,5000,10000,20000,50000]
print(changeOptions(n,S))

#14

https://repl.it/JtaB/1


#15

A reminder to any members who did not post their formatted code, please post it so your entry is not disqualified. Remember to also explain your logic.


#16

My solution (in java) can be found here. The logic is that at each level of recursion, the code takes each successive value in sValues and sums the number of options with and without that number included in the total sum. If the number is added to the sum (subtracted from n), the program will not increment index because the number could be added again at the next level of recursion. There are three base cases to handle the three options that indicate that a chain of recursion has reached its end. First, if n == 0, it means that the combination adds up because at each level of recursion, numbers were subtracted that all added up to n. If n<0, it means that the combination does not work because the total subtracted was greater than n. Finally, if index has reached the length of sValues, but n is greater than 0, the combination is too small because n is not 0, but there are no more values of s to add. The helper method is simply to add a 0 index for recursion.

int changeOptions(int n, int[] sValues){
  changeOptionsRecur(n,sValues,0);
}
static int changeOptionsRecur(int n, int[] sValues,int index){
        if(n == 0){
            return 1;
        }
        if(n<0){
            return 0;
        }
        if(index == sValues.length){
            return 0;
        }
        return changeOptionsRecur(n - sValues[index],sValues,index)+changeOptionsRecur(n,sValues,index+1);
}

#17

I now the challenge is over, but wanted to post my Javascript solution - unfortunately had to use external library to get BigInteger. I used recursive approach with saving the results for each invocation to save computation time, works pretty quick.

I have read the rules just after posting this, this code does not work with repl.it because it uses Map class from ES6. Would have to rewrite it to work, so I leave it just for reference.

const bigInt = require('big-integer');

let S = [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000];
const n = 26730;

changeOptionsMap = new Map();

function changeOptions(n, S) {
  let nString = JSON.stringify({
    n,
    S
  });
  options = bigInt.zero;

  if (changeOptionsMap.has(nString)) {
    get = changeOptionsMap.get(nString);
    return get;
  } else {
    for (var variable of S) {
      let temp = n - variable;
      if (temp > 0) {
        options = bigInt(options.toString()).add(changeOptions(temp, S.slice(S.indexOf(variable))));
      } else if (temp == 0) {
        options = bigInt(options.toString()).add(1);
      }
    }
  }


  changeOptionsMap.set(nString, options.toString());
  return options.toString();
}

changeOptions(n, S.reverse());
console.log(changeOptionsMap);



#18

Some really great replies to this challenge, very impressed!

Most people realised the best way to attack this problem is through recursion, and more specifically dynamic programming. Specifically to allow large numbers to be computed an array should be kept of pre-computed values.

For this reason, we have three very quick programs in Python: @cmecklenborg, @boglee28 and @chipcoder14919

They all run within milliseconds of each other, so all three of you are join winners, very well done :slight_smile: Look out for the new challenge that has just been released!