change.clj

gistfile1.clj

(def denoms [2000 1000 500 100 25 10 5 1])

(defn make-change
  ([amt] (make-change amt denoms {}))
  ([amt denoms r]
     (if (zero? amt)
       r
       (let [[f :as denoms] (drop-while #(> % amt) denoms)
             [n amt] ((juxt quot rem) amt f)]
         (recur amt denoms (assoc-in r [f] n))))))

(comment
  ;; 43ms for worst case
  (dotimes [_ 10]
    (time
     (dotimes [_ 1e4]
       (make-change 1999))))
  )