Project Euler Problem 4 Solved with Javascript

Welcome to another edition of Jared rediscovers grade school math! Today we are tackling problem 4 of Project Euler. We are going to talk about Palindromes and for loops. Let's get into it!

Problem Discussion

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Video Version

If you like to watch rather than read, check out the video that accompanies this article. If not, keep reading!

Statement

Find the largest palindrome made from the product of two 3-digit numbers.

Palindrome

A word that reads the same forwards as backwards. Example is 9009 or racecar.

Solution

The approach I'm taking is both brute force and algorithmic.

Steps

1. Determine the highest products to work from, e.g. 99 x 99
2. Multiply the highest products together
3. Reduce right number by one
   1. Check if palindrome
   2. Repeat until reaching 1
4. Reduce left number by one.
   1. Check if palindrome
   2. Repeat step 3
5. If at any time, number is palindrome, return that number.

Solution

For this solution, I am going to reach for my old friend: functional programming. First let's create a function that checks if a string is a palindrome.

Palindrome?

Our friend Javascript has a ton of helper functions in dealing with strings. Unfortunately, this means that we have to convert our number to a string, then reconvert it back after we've checked it. It takes some extra time, but it's not to computationaly expensive.

    function isPalindrome(num) {
      // get reverse
      let reversed = String(num)
        .split('')
        .reverse()
        .join('');
      // return equality check
      return Number(reversed) === num;
    }

Tale of Two Loops

In order to check all numbers, we have to check all products from 99 x 99 → 1 x 1. To accomplish this, we're going to loop the right number inside of the left number, i.e. 99 x 99 → 99 x 98...and so forth.

    function largestPalindromeProduct(n) {
      let highest = 0;
      // Find largest number
      let largestNum = '9';
      largestNum += Number(largestNum.repeat(n - 1));
      largestNum = Number(largestNum);

        // loop left number
      for (let i = largestNum; i > 0; i--) {
            // loop right number
        for (let j = largestNum; j > 0; j--) {
          let product = i * j;
                // check if palindrome
          if (isPalindrome(product)) {
            if (product > highest) highest = product;
            // we have the highest palindrome for this set, skip to next loop
            break;
          }
        }
      }
        // return the highest palindrome we found
      return highest;
    }

Full Solution

    function isPalindrome(num) {
      // get reverse
      let reversed = String(num)
        .split('')
        .reverse()
        .join('');
      // return equality check
      return Number(reversed) === num;
    }

    function largestPalindromeProduct(n) {
      let highest = 0;
      // Find largest number
      let largestNum = '9';
      largestNum += Number(largestNum.repeat(n - 1));
      largestNum = Number(largestNum);

        // loop left number
      for (let i = largestNum; i > 0; i--) {
            // loop right number
        for (let j = largestNum; j > 0; j--) {
          let product = i * j;
                // check if palindrome
          if (isPalindrome(product)) {
            if (product > highest) highest = product;
            // we have the highest palindrome for this set, skip to next loop
            break;
          }
        }
      }
        // return the highest palindrome we found
      return highest;
    }

Final Thoughts

This approach includes both a minor algorithm, in that it skips over any numbers below a certain threshold and brute force. It will check all the highest palindromes from 99 x 99 to 1 x 1.

There is definitely room for improvement here. In fact I found a couple out there that are better than mine, but this works for now.

If you have any suggestions or adjustments you think would make it better, feel free to leave a comment!

As always, happy coding.

Resources

https://www.xarg.org/puzzle/project-euler/problem-4/

https://github.com/Matt-1123/project-euler/blob/master/solutions.js

Comments

[Dhurak]

A few possible optimizations:

• Inner loop only has to iterate from i to 0 instead of largestNum to 0
• We can break out of inner loop whenever product drops below highest

With both optimizations we go from almost 600k palindrome tests to about 6k tests with largestNum equal to 999.

[Jared]

Hi Dhurak! I think I'm confused by what you mean. In your scenario, what is the i value?

[Dhurak]

for (let j = largestNum; j > 0; j--)

can become:

for (let j = i; j > 0; j--)

The inner loop does not have to start from the very beginning every time.
First set would be 99x99, 99x98, 99x97... 99x1
Second set would be 98x98, 98x97, 98x96... 98x1
Third set: 97x97, 97x96, 97x95... 97x1

In second set you don't test 98x99 because you already tested 99x98 in first set.

[Jared]

Ohhh, I see. That's genius. Thank you!