Skip to content

Instantly share code, notes, and snippets.

@swannodette

swannodette/gist:1074818

Created July 10, 2011 18:38
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save swannodette/1074818 to your computer and use it in GitHub Desktop.
Save swannodette/1074818 to your computer and use it in GitHub Desktop.
Download ZIP
change.clj
Raw
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))))
)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment