Skip to content

Instantly share code, notes, and snippets.

@gdeer81
Last active August 4, 2017 22:00
Show Gist options
  • Save gdeer81/0a3254afa21c853c87a0635e09063504 to your computer and use it in GitHub Desktop.
Save gdeer81/0a3254afa21c853c87a0635e09063504 to your computer and use it in GitHub Desktop.
beginner performance bug
;;this works until you pass in ridiculously large numbers
;; the for loop lets me try all of the numbers in the collection with each other
(defn find-the-pairs [n]
"takes an upper bound and returns all the pairs of numbers where
(* x y) equals the sum of the entire collection without x and y
(find-the-pairs 26) => [[15 21] [21 15]]
"
(let [coll (take n (iterate inc 1))
coll-sum (apply + coll)]
(reduce
(fn [result [num1 num2]]
(if (= (- coll-sum (+ num1 num2)) (* num1 num2))
(conj result [num1 num2])
result))
[] (for [i coll j coll] [i j]))))
;;this version works on ridiculously large numbers
(defn find-the-pairs2 [^long n]
(let [^long coll-sum (/ (* n (inc n)) 2)
pair? (fn [i] (let [j (/ (- coll-sum i) (+ i 1))] (when (and (not (ratio? j))
(<= j n)
(not= i j)) [i (long j)])))]
(vec (remove nil? (map pair? (range 1 (inc n)))))))
;;this is the best version returns in nanoseconds on values over 1 million
(defn find-the-pairs3 [^long n]
(let [^long coll-sum (/ (* n (inc n)) 2)
valid-pair? (fn [i] (let [j (/ (- coll-sum i) (+ i 1))] (when (and (not (ratio? j))
(<= j n)
(not= i j)) [i j])))]
(keep valid-pair? (range 1 (inc n)))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment