{"id":609,"date":"2012-08-08T20:44:58","date_gmt":"2012-08-09T00:44:58","guid":{"rendered":"http:\/\/www.joshho.com\/blog\/?p=609"},"modified":"2012-09-07T16:07:40","modified_gmt":"2012-09-07T20:07:40","slug":"project-euler-problem-53","status":"publish","type":"post","link":"https:\/\/www.joshho.com\/blog\/2012\/08\/08\/project-euler-problem-53\/","title":{"rendered":"Project Euler &#8211; Problem 53"},"content":{"rendered":"<p>Problem 53: How many, not necessarily distinct, values of nCr, for 1 <= n <= 100, are greater than one-million?\n<!--more--><br \/>\n<code><\/p>\n<pre lang='java'>\r\nclass runner\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\r\n\t\tint[][] triangle = new int[98][98];\/\/5+2=7, 98+2=100\r\n\t\t\/\/setup\r\n\t\tfor(int i=0;i<triangle.length;i++){\r\n\t\t\ttriangle[0][i] = i+2;\r\n\t\t\ttriangle[i][0] = i+2;\r\n\t\t}\r\n\t\t\r\n\t\tint count = 0;\r\n\t\tfor(int j=1;j<triangle.length;j++){\r\n\t\t\tfor(int i=1;i<=triangle.length-j;i++){\r\n\t\t\t\tint sum = triangle[j][i-1]+triangle[j-1][i];\r\n\t\t\t\t\/\/System.out.print(sum+\"\\t\");\r\n\t\t\t\tif(sum > 1000000){\r\n\t\t\t\t\tcount += j-i+1;\r\n\t\t\t\t\ttriangle[j][i] = 1000000;\r\n\t\t\t\t\tbreak;\r\n\t\t\t\t}\r\n\t\t\t\ttriangle[j][i] = sum;\r\n\t\t\t}\r\n\t\t\t\/\/System.out.println();\r\n\t\t}\r\n\t\tSystem.out.println(\"c:\"+count);\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 53: How many, not necessarily distinct, values of nCr, for 1 <= n <= 100, are greater than one-million?\n\n<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[56],"tags":[],"class_list":["post-609","post","type-post","status-publish","format-standard","hentry","category-project-euler"],"_links":{"self":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/609","targetHints":{"allow":["GET"]}}],"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=609"}],"version-history":[{"count":2,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/609\/revisions"}],"predecessor-version":[{"id":747,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/609\/revisions\/747"}],"wp:attachment":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/media?parent=609"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/categories?post=609"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/tags?post=609"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}