Project Euler Problem 4 Solved with Javascript

Tags: javascript, projecteuler, tutorial, challenge
Published: 2020-02-10 16:30:25


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!

{% youtube 2IXX6P8MgvA %}

## 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.
```js
    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.
```js
    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
```js
    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