[LeetCode/LintCode] Largest Palindrome Product

Barry_Ng 發布于2019-08-15 18:16 / 2404人閱讀

Problem

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

Since the result could be very large, you should return the largest palindrome mod 1337.

Example

Input: 2
Output: 987
Explanation: 99 x 91 = 9009, 9009 % 1337 = 987

Solution

public class Solution {
    /**
     * @param n: the number of digit
     * @return: the largest palindrome mod 1337
     */
    public int largestPalindrome(int n) {
        // when n == 1, largest palindrome would be single-digit
        if (n == 1) return 9;
        
        // get the maximum and the minimum factors
        long maxFactor = (long)Math.pow(10, n)-1;
        long minFactor = (long)Math.pow(10, n-1);
        
        // get the largest product first, then use the first half to create palindrome
        long maxProduct = (long)maxFactor * (long)maxFactor;
        long maxHalf = maxProduct / (long)Math.pow(10, n);

        // initialize result palindrome to 0, and set the flag to check if result found and end the while loop
        long palindrome = 0;
        boolean palindromeFound = false;
        
        while (!palindromeFound) {
            // generate the latest largest palindrome in each cycle
            palindrome = generatePalindrome(maxHalf);
            
            for (long i = maxFactor; i >= minFactor; i--) {
                // the generated palindrome cannot be larger than maxFactor * maxFactor
                if (palindrome / i > i || palindrome / maxFactor > maxFactor) {
                    break;
                }
                
                if (palindrome % i == 0) {
                    palindromeFound = true;
                    break;
                }
            }
            //when for loop ends, decrease maxHalf by 1 to generate the next palindrome
            maxHalf--;
        }
        
        return (int)(palindrome % 1337);
    }
    
    public long generatePalindrome(long num) {
        String str = String.valueOf(num) + new StringBuilder().append(num).reverse().toString();
        return Long.parseLong(str);
    }
}

GPU云服務器云服務器 Largest palindrome Product 阿里大魚product

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/69717.html

[LeetCode/LintCode] Valid Palindrome

Valid Palindrome Problem Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. Example A man, a plan, a canal: Panama is a palindrome. race a ca...

Ververica 2019-08-14 15:16 評論0 收藏0
16 道 JavaScript 基礎算法 - freeCodeCamp

#1. Reverse a String Reverse the provided string. You may need to turn the string into an array before you can reverse it. Your result must be a string. function reverseString(str/*:string*/) { if ...

yintaolaowanzi 2019-08-21 17:19 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
leetcode部分題目答案之JavaScript版

摘要：自己沒事刷的一些的題目，若有更好的解法，希望能夠一起探討項目地址自己沒事刷的一些LeetCode的題目，若有更好的解法，希望能夠一起探討 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...

alphahans 2019-08-21 16:20 評論0 收藏0
Leetcode[152] Maximum Product Subarray

摘要：復雜度思路要保留一個到某一位來看的最大值和最小值。因為在數組中有負數的出現，所以到這一位為止的能得到的最大值，可能是由之前的最大值和這個數相乘得到，也可能是最小值和這個數相乘得到的。 Leetcode[152] Maximum Product Subarray Find the contiguous subarray within an array (containing at le...

_ipo 2019-08-14 16:49 評論0 收藏0