Finds the largest palindromic number that can be made by multiplying two numbers of a specified length together.

FactorFinder.php

<?php

/**
 * User: frank.steinberg
 * Date: 7/30/18
 * Time: 11:57 AM
 */

class FactorFinder
{
    /**
     * Returns the largest Palindrome that can created by multiplying two factors of a given length.
     * @param integer $factorLength The length (in digits) of the desired factors.
     * @return integer
     */
    public function run($numberOfDigitsForEachFactor)
    {
        $maxFactor = $this->getLargestNumberWithSpecificLength($numberOfDigitsForEachFactor);
        $minFactor = $this->getLargestNumberWithSpecificLength($numberOfDigitsForEachFactor - 1) + 1;
        $maxProduct = $maxFactor * $maxFactor;

        if ($this->isPalindrome($maxProduct)) {
            echo $maxFactor . ' x ' . $maxFactor . ' = ' . $maxProduct;
            return $maxProduct;
        }

        $currentPalindromicNumber = $this->getPreviousPalindromeThroughBruteForce($maxProduct);

        try {
            while ($currentPalindromicNumber >= $minFactor * $minFactor ) {
                echo "Trying: {$currentPalindromicNumber}" . PHP_EOL;
                $factors = $this->getFactors($currentPalindromicNumber, $maxFactor, $minFactor);
                if ($factors) {
                    echo join(' x ', $factors) . ' = ' . $currentPalindromicNumber . PHP_EOL;
                    return $currentPalindromicNumber;
                }
                $currentPalindromicNumber = $this->getPreviousPalindromeFromCurrentPalindrome($currentPalindromicNumber);
            }
            throw new Exception('Could not find a palindrome for that factor length.');
        } catch (\Exception $e) {
            echo "Could not find {$numberOfDigitsForEachFactor}-digit factors that created a palindromic number when multiplied." . PHP_EOL;
            return null;
        }
    }

    /**
     * Returns true if the given number is a palindromic number.
     * Ex. isPalindrome(1358531) returns true.
     * @param integer $number A number.
     * @return boolean
     */
    public function isPalindrome(int $number)
    {
        return (string) $number === strrev((string) $number);
    }

    /**
     * Gets the previous palindromic number before the provided palindromic number.
     * @param integer $number The current number.
     * @return int
     */
    public function getPreviousPalindromeFromCurrentPalindrome(int $currentPalindrome)
    {
        $length = strlen((string)$currentPalindrome);

        $digits = array_slice(
            str_split((string) $currentPalindrome),
            0,
            (int) ($length % 2 !== 0) ? (($length + 1) / 2) : ($length / 2)
        );

        end($digits);
        while (key($digits) >= 0) {
            if( $digits[key($digits)] > 0){
                $digits[key($digits)]--;
                break;
            }

            if (key($digits) === 0) {
                throw new \Exception('No more palindromes.');
            }

            $digits[key($digits)] = 9;
            prev($digits);
        }

        if ($length %2 === 0) {
            return (int) join('', $digits) . strrev(join('', $digits));
        } else {
            return (int) join('', $digits) . substr(strrev(join('', $digits)), 1);
        }

    }

    /**
     * Returns factors for a given number that are between a given min and max.
     * @param integer $number    The number.
     * @param integer $maxFactor The max factor size.
     * @param integer $minFactor The min factor size.
     * @return array|null
     */
    public function getFactors(int $number, int $maxFactor, int $minFactor){
        for ($factor1 = (int) sqrt(abs($number)); $factor1 >= $minFactor ; $factor1--)
        {
            if (
                $number % $factor1 == 0
                && ($factor2 = $number / $factor1) <= $maxFactor
            ) {
                return [
                    $factor1,
                    $factor2
                ];
            }
        }
        return null;
    }

    /**
     * Returns the largest possible number of a specific length.
     * @param integer $length The length of the number to be returned.
     * @return int
     */
    protected function getLargestNumberWithSpecificLength(int $length): int
    {
        $maxFactorDigits = [];
        for ($i = 0; $i < $length; $i++) {
            $maxFactorDigits[] = 9;
        }
        $maxFactor = (int)join('', $maxFactorDigits);
        return $maxFactor;
    }

    /**
     * @param int $number
     * @return int
     */
    protected function getPreviousPalindromeThroughBruteForce(int $number): int
    {
        $number--;
        while ((!$this->isPalindrome($number)) && ($number > 0)) {
            $number--;
        }
        return $number;
    }
}