{"id":529,"date":"2012-08-04T23:21:57","date_gmt":"2012-08-05T03:21:57","guid":{"rendered":"http:\/\/www.joshho.com\/blog\/?p=529"},"modified":"2012-09-07T16:12:44","modified_gmt":"2012-09-07T20:12:44","slug":"project-euler-problem-33","status":"publish","type":"post","link":"https:\/\/www.joshho.com\/blog\/2012\/08\/04\/project-euler-problem-33\/","title":{"rendered":"Project Euler &#8211; Problem 33"},"content":{"rendered":"<p>Problem 33:<br \/>\nThe fraction 49\/98 is a curious fraction, as 49\/98 = 4\/8, obtained by cancelling the 9s.<\/p>\n<p>We shall consider fractions like, 30\/50 = 3\/5, to be trivial examples.<\/p>\n<p>There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.<\/p>\n<p>If the product of these four fractions is given in its lowest common terms, find the value of the denominator.<br \/>\n<!--more--><br \/>\n<code><\/p>\n<pre lang='java'>\r\n\r\npublic class Fraction{\r\n\tint t,b;\r\n\tpublic Fraction(int top, int bot){\r\n\t\tt=top;b=bot;\r\n\t}\r\n\tpublic Fraction multiply(int x){\r\n\t\treturn new Fraction(t*x,b*x);\r\n\t}\r\n\t\r\n\tpublic int getNumerator(){\r\n\t\treturn t;\r\n\t}\r\n\tpublic int getDenominator(){\r\n\t\treturn b;\r\n\t}\r\n\t\r\n\tpublic int compareTo(Fraction other){\r\n\t\tif(other.getNumerator() == t && other.getDenominator() == b) return 0;\r\n\t\treturn -1;\r\n\t}\r\n\tpublic String toString(){\r\n\t\treturn t+\"\/\"+b;\r\n\t}\r\n}\r\n<\/pre>\n<p><\/code><\/p>\n<p>Actual Code:<br \/>\n<code><\/p>\n<pre lang='java'>\r\nimport java.util.Collections;\r\nimport java.util.HashMap;\r\nimport java.util.Vector;\r\n\r\nclass runner\r\n{\r\n\tprivate static boolean storageContainsFraction(HashMap<Fraction, Vector<Fraction>> storage, Fraction current){\r\n\t\tfor(Fraction key : storage.keySet()){\r\n\t\t\tVector<Fraction> sub_array = storage.get(key);\r\n\t\t\tfor(int i=0; i<sub_array.size();i++){\r\n\t\t\t\tif(current.compareTo(sub_array.get(i)) == 0) return true;\r\n\t\t\t}\r\n\t\t}\r\n\t\t\r\n\t\treturn false;\r\n\t}\r\n\t\r\n\tprivate static Fraction removeSameDigit(int n, int d){\r\n\t\tint n1 = n%10, n2 = n\/10;\r\n\t\tint d1 = d%10, d2 = d\/10;\r\n\t\t\r\n\t\tif(n1 == d1 &#038;&#038; n1!=0){\r\n\t\t\treturn new Fraction(n2, d2);\r\n\t\t}else if(n1 == d2 &#038;&#038; n1!=0){\r\n\t\t\treturn new Fraction(n2, d1);\r\n\t\t}else if(n2 == d1 &#038;&#038; n2!=0){\r\n\t\t\treturn new Fraction(n1, d2);\r\n\t\t}else if(n2 == d2 &#038;&#038; n2!=0){\r\n\t\t\treturn new Fraction(n1, d1);\r\n\t\t}\r\n\t\treturn null;\r\n\t}\r\n\t\r\n\tpublic static void main (String[] args) throws java.lang.Exception\r\n\t{\r\n\t\tlong time = System.currentTimeMillis();\r\n\t\tHashMap<Fraction, Vector<Fraction>> storage = new HashMap<Fraction, Vector<Fraction>>(); \r\n\t\t\r\n\t\t\/\/Setup\r\n\t\tfor(int denominator = 2; denominator < 50; denominator++){\/\/49*2 = 98, the limit of doubledigits\r\n\t\t\tfor(int numerator = 1; numerator < denominator; numerator++){\r\n\t\t\t\tFraction current = new Fraction(numerator, denominator);\r\n\t\t\t\tif(storageContainsFraction(storage, current)) continue;\r\n\t\t\t\t\r\n\t\t\t\t\/\/System.out.print(current + \" \");\r\n\t\t\t\t\r\n\t\t\t\tVector<Fraction> sub_array = new Vector<Fraction>();\r\n\t\t\t\tsub_array.add(current);\r\n\t\t\t\t\r\n\t\t\t\tint i=2;\r\n\t\t\t\tFraction multiplied = current.multiply(i);\r\n\t\t\t\twhile(multiplied.getDenominator() < 100 &#038;&#038; multiplied.getNumerator() < 100){\r\n\t\t\t\t\tsub_array.add(multiplied);\r\n\t\t\t\t\t\r\n\t\t\t\t\t\/\/System.out.print(multiplied + \" \");\r\n\t\t\t\t\t\r\n\t\t\t\t\ti++;\r\n\t\t\t\t\tmultiplied = current.multiply(i);\r\n\t\t\t\t}\r\n\t\t\t\t\/\/System.out.println();\r\n\t\t\t\t\r\n\t\t\t\tstorage.put(current, sub_array);\r\n\t\t\t}\t\r\n\t\t}\r\n\r\n\t\tVector<Integer> denominatorAnswer = new Vector<Integer>();\r\n\t\t\r\n\t\t\/\/Check\r\n\t\tfor(Fraction key : storage.keySet()){\r\n\t\t\tVector<Fraction> sub_array = storage.get(key);\r\n\t\t\tfor(int i=0; i<sub_array.size();i++){\r\n\t\t\t\tFraction current = sub_array.get(i);\r\n\t\t\t\tif(current.getNumerator() < 10 || current.getDenominator() < 10) continue; \/\/Not double digit.\r\n\t\t\t\tFraction simplified = removeSameDigit(current.getNumerator(), current.getDenominator());\r\n\t\t\t\tif(simplified == null) continue;\/\/No same digit\r\n\t\t\t\t\/\/System.out.println(key+\"\\t\"+current+\"\\t\"+simplified);\r\n\t\t\t\tfor(int j=0;j<i;j++){\r\n\t\t\t\t\tif(simplified.compareTo(sub_array.get(j)) == 0){\r\n\t\t\t\t\t\tdenominatorAnswer.add(simplified.getDenominator());\r\n\t\t\t\t\t\tSystem.out.println(key+\"\\t\"+current+\"\\t\"+simplified);\r\n\t\t\t\t\t}\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t}\r\n\t\t\r\n\t\tint prod = 1;\r\n\t\tCollections.sort(denominatorAnswer);\r\n\t\tfor(int i=0;i<denominatorAnswer.size(); i++){\r\n\t\t\tint c = denominatorAnswer.get(i);\r\n\t\t\t\r\n\t\t\tboolean x = false;\r\n\t\t\tfor(int j=0;j<i-1;j++){\r\n\t\t\t\tif(c % denominatorAnswer.get(j) == 0)\r\n\t\t\t\t\tx = true;\r\n\t\t\t}\r\n\t\t\tif(!x) prod *= c;\r\n\t\t}\r\n\t\tSystem.out.println(\"Product: \"+prod);\r\n\t\t\r\n\t\tSystem.out.println(\"time: \"+(System.currentTimeMillis() - time));\r\n\t}\r\n}\r\n<\/pre>\n<p><\/code><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem 33:<br \/>\nThe fraction 49\/98 is a curious fraction, as 49\/98 = 4\/8, obtained by cancelling the 9s.<\/p>\n<p>We shall consider fractions like, 30\/50 = 3\/5, to be trivial examples.<\/p>\n<p>There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.<\/p>\n<p>If the product of these four fractions is given in its lowest common terms, find the value of the denominator.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[56],"tags":[],"_links":{"self":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/529"}],"collection":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/comments?post=529"}],"version-history":[{"count":0,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/529\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/media?parent=529"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/categories?post=529"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/tags?post=529"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}