[LeetCode/LintCode] Largest Palindrome Product

Barry_Ng 发布于2019-08-15 18:16 / 2322人阅读

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);
    }
}

私有云云服务器 Largest palindrome Product 阿里大鱼product

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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