{"id":556,"date":"2012-08-06T12:10:17","date_gmt":"2012-08-06T16:10:17","guid":{"rendered":"http:\/\/www.joshho.com\/blog\/?p=556"},"modified":"2012-09-07T16:10:24","modified_gmt":"2012-09-07T20:10:24","slug":"project-euler-problem-40","status":"publish","type":"post","link":"https:\/\/www.joshho.com\/blog\/2012\/08\/06\/project-euler-problem-40\/","title":{"rendered":"Project Euler – Problem 40"},"content":{"rendered":"

Problem 40: An irrational decimal fraction is created by concatenating the positive integers:
\n

0.123456789101112131415161718192021...<\/code><\/center>
\nIt can be seen that the 12th digit of the fractional part is 1.<\/p>\n

If dn represents the nth digit of the fractional part, find the value of the following expression.
\n

d1 x d10 x d100 x d1000 x d10000 x d100000 x d1000000<\/code><\/center>
\n
\n<\/p>\n
\r\nclass runner\r\n{\r\n\tprivate static int slow_logic(int n){\r\n\t\tString x = \"\";\r\n\t\tint i = 1;\r\n\t\twhile(x.length() <= n){\r\n\t\t\tx+=i;\r\n\t\t\ti++;\r\n\t\t}\r\n\t\treturn x.charAt(n) - 48;\r\n\t}\r\n\tprivate static int fast_logic(int n){\r\n\t\tint n_tens = 0;\r\n\t\tint next_sub = 0, sub = 0;\r\n\t\tdo{\r\n\t\t\tn_tens++;\r\n\t\t\tsub = next_sub;\r\n\t\t\tnext_sub = next_sub + 9*n_tens*(int)Math.pow(10, (n_tens-1));\r\n\t\t}while(n > next_sub);\r\n\t\tif(n>9)n--;\r\n\t\tn-=sub;\r\n\r\n\t\tint r = n%(n_tens);\r\n\t\tint out =  n_tens == 1 ? 0 : (int) Math.pow(10, n_tens-1);\r\n\t\tint d=n\/n_tens;\r\n\t\tout = out+d;\r\n\r\n\t\tString lazy = \"\"+out;\r\n\t\treturn lazy.charAt(r)-48;\r\n\t}\r\n\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[] find = {1,10,100,1000,10000,100000,1000000};\r\n\r\n\t\tint prod = 1;\r\n\t\tfor(int i: find){\r\n\t\t\tprod *= fast_logic(i);\r\n\t\t\t\/\/prod *= slow_logic(i);\r\n\t\t}\r\n\t\tSystem.out.println(prod);\r\n\r\n\t\tSystem.out.println(\"time: \"+(System.currentTimeMillis() - time));\r\n\t}\r\n}\r\n<\/pre>\n
<\/code>
\nNote: Not sure why
\n
next_sub = next_sub + 9*n_tens*(int)Math.pow(10, (n_tens-1));<\/code><\/center>
\ncauses the code to require:
\n
if(n>9)n--;<\/code><\/center>
\nIf you do find out how to remove if(n>9)n--;<\/code>, please let me know.<\/p>\n","protected":false},"excerpt":{"rendered":"
Problem 40: An irrational decimal fraction is created by concatenating the positive integers:
\n
0.123456789101112131415161718192021...<\/code><\/center>
\nIt can be seen that the 12th digit of the fractional part is 1.<\/p>\n
If dn represents the nth digit of the fractional part, find the value of the following expression.
\n
d1 x d10 x d100 x d1000 x d10000 x d100000 x d1000000<\/code><\/center><\/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\/556"}],"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=556"}],"version-history":[{"count":0,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/posts\/556\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/media?parent=556"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/categories?post=556"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.joshho.com\/blog\/wp-json\/wp\/v2\/tags?post=556"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}