{"id":95,"date":"2013-01-17T21:40:27","date_gmt":"2013-01-18T05:40:27","guid":{"rendered":"http:\/\/willclausen.com\/?p=95"},"modified":"2013-01-17T21:48:49","modified_gmt":"2013-01-18T05:48:49","slug":"solution-project-euler-problem-4","status":"publish","type":"post","link":"http:\/\/willclausen.com\/?p=95","title":{"rendered":"Solution: Project Euler Problem 4"},"content":{"rendered":"<p>The Problem:<\/p>\n<p style=\"padding-left: 30px;\">A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91\u00a0<img loading=\"lazy\" decoding=\"async\" alt=\"\u00d7\" src=\"http:\/\/projecteuler.net\/images\/symbol_times.gif\" width=\"9\" height=\"9\" border=\"0\" \/>\u00a099.<\/p>\n<p style=\"padding-left: 30px;\">Find the largest palindrome made from the product of two 3-digit numbers.<\/p>\n<p>My solution (in C++):<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n\r\n\/\/ Author: Will Clausen\r\n\/\/\r\n\/\/ Date: Jan 7, 2013\r\n\/\/\r\n\/\/ This program will solve Problem 4 of Project\r\n\/\/ Euler\r\n\r\n\/\/ INCLUDES\r\n\r\n#include &lt;cstddef&gt;\r\n#include &lt;cmath&gt;\r\n#include &lt;set&gt;\r\n#include &lt;iostream&gt;\r\n#include &lt;sstream&gt; \/\/ For converting numbers to strings.\r\n\r\nusing namespace std;\r\n\r\n\/\/ DECLARATIONS (could be put in a header, but there's only 2\r\n\/\/ so I'll spare myself the trouble).\r\n\r\nsize_t problem4(size_t numDigits);\r\nbool isPalindrome(size_t Num);\r\n\r\n\/\/ IMPLEMENTATIONS\r\n\r\n\/\/ This function will return the largest palindromic number that is the product\r\n\/\/ of two numbers with numDigits digits.\r\nsize_t problem4(size_t numDigits)\r\n{\r\n\tsize_t startingNum = pow(10, numDigits-1);\r\n\tsize_t endingNum = pow(10, numDigits);\r\n\tsize_t nextNum;\r\n\tsize_t largestPalindrome = startingNum;\r\n\r\n\t\/\/ Generate all palindromes and add them to a set.\r\n\tfor (size_t x = startingNum; x &lt; endingNum; ++x) {\r\n\t\tfor (size_t y = startingNum; y &lt; endingNum; ++y) {\r\n\t\t\tnextNum = x*y;\r\n\t\t\tif (isPalindrome(nextNum)) {\r\n\t\t\t\tif (nextNum &gt; largestPalindrome) {\r\n\t\t\t\t\tlargestPalindrome = nextNum;\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n\r\n\treturn largestPalindrome;\r\n}\r\n\r\n\/\/ Helper function to determine if a number is a palindromic number\r\nbool isPalindrome(size_t Num) {\r\n\t\/\/ Convert the number to a string\r\n\tstring Number;\r\n\tstringstream convert;\r\n\tconvert &lt;&lt; Num;\r\n\tNumber = convert.str();\r\n\tsize_t NumLen = Number.length();\r\n\r\n\t\/\/ Check the string\r\n\tfor (size_t i = 0; i &lt; NumLen\/2; ++i) {\r\n\t\tif (Number&#x5B;i] != Number&#x5B;NumLen - 1 - i])\r\n\t\t\treturn false;\r\n\t}\r\n\r\n\treturn true;\r\n}\r\n\r\n\/\/ Solution: 906609\r\n<\/pre>\n<p>Comment if you know a way to think about this problem that leads to a faster solution. In particular, I wonder if there&#8217;s a faster way to generate possible numbers than brute-force search.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The Problem: A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91\u00a0\u00a099. Find the largest palindrome made from the product of two 3-digit numbers. My solution (in C++): \/\/ Author: Will Clausen \/\/ \/\/ Date: Jan 7, 2013 \/\/ \/\/ This program [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[18],"tags":[9,23,19],"class_list":["post-95","post","type-post","status-publish","format-standard","hentry","category-project-euler-solutions","tag-january2013","tag-project-euler-problem-4","tag-project-euler-solution"],"_links":{"self":[{"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/posts\/95","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/willclausen.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=95"}],"version-history":[{"count":2,"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/posts\/95\/revisions"}],"predecessor-version":[{"id":101,"href":"http:\/\/willclausen.com\/index.php?rest_route=\/wp\/v2\/posts\/95\/revisions\/101"}],"wp:attachment":[{"href":"http:\/\/willclausen.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=95"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/willclausen.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=95"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/willclausen.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=95"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}