package leetcode;

/**
 * https://leetcode.com/problems/largest-palindrome-product/
 */
public class Problem479 {
    public int largestPalindrome(int n) {
        StringBuilder largestStr = new StringBuilder();
        for (int i = 0; i < n; i++) {
            largestStr.append(9);
        }
        StringBuilder smallestStr = new StringBuilder();
        smallestStr.append(1);
        for (int i = 1; i < n; i++) {
            smallestStr.append(0);
        }
        long largest = Long.parseLong(largestStr.toString());
        long smallest = Long.parseLong(smallestStr.toString());
        long max = 0;
        for (long i = largest; i >= smallest; i--) {
            for (long j = largest; j >= smallest; j--) {
                long num = i * j;
                if (isPalindrome(Long.toString(num))) {
                    max = Math.max(max, num);
                }
            }
        }
        return (int) (max % 1337);
    }

    private static boolean isPalindrome(String str) {
        for (int i = 0, j = str.length() - 1; i < j; i++, j--) {
            if (str.charAt(i) != str.charAt(j)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Problem479 prob = new Problem479();
        System.out.println(prob.largestPalindrome(1)); // 9
        System.out.println(prob.largestPalindrome(2)); // 987
        System.out.println(prob.largestPalindrome(3)); // 123
        System.out.println(prob.largestPalindrome(4)); // 597
        System.out.println(prob.largestPalindrome(5)); // 677
        System.out.println(prob.largestPalindrome(6)); // 1218
        System.out.println(prob.largestPalindrome(7)); // 877
        System.out.println(prob.largestPalindrome(8)); // 475
    }
}

@@ -145,24 +145,78 @@
 me(int n) %7B%0A
+        if (n == 1) %7B%0A            return 9;%0A        %7D%0A
         Stri
@@ -661,153 +661,344 @@
 x = 
-0;%0A        for (long i = largest; i %3E= smallest; i--) %7B%0A            for (long j = largest; j %3E= smallest; j--) %7B%0A                long num = i * j
+largest * largest;%0A        String maxStr = Long.toString(max);%0A        long maxSub = Long.parseLong(maxStr.substring(0, maxStr.length() / 2));%0A        while (true) %7B%0A            String first = Long.toString(maxSub);%0A            String second = new StringBuilder(%22%22 + maxSub).reverse().toString();%0A            String str = first + second
 ;%0A  
@@ -1003,28 +1003,24 @@
             
-    
 if (isPalind
@@ -1028,76 +1028,122 @@
 ome(
-Long.toString(num))) %7B%0A                    max = Math.max(max, num);
+str)) %7B%0A                long l = Long.parseLong(str);%0A                for (long j = largest; j %3E= smallest; j--) %7B
 %0A   
@@ -1159,23 +1159,29 @@
     
-%7D%0A
     
-        %7D
+long div = l / j;
 %0A   
@@ -1181,34 +1181,36 @@
  j;%0A        
-%7D%0A
+    
         
 return (int)
@@ -1201,211 +1201,209 @@
     
-return (int) (max %25 1337);%0A    %7D%0A%0A    private static boolean isPalindrome(String str) %7B%0A        for (int i = 0, j = str.length() - 1; i %3C j; i++, j--) %7B%0A            if (str.charAt(i) != str.charAt(j)) %7B%0A
+if (div %3E max %7C%7C j * j %3C l) %7B%0A                        break;%0A                    %7D%0A                    long mod = l %25 j;%0A                    if (mod == 0 && Long.toString(div).length() == n) %7B%0A        
     
@@ -1425,15 +1425,34 @@
 urn 
-false;%0A
+(int) (l %25 1337);%0A        
     
@@ -1473,621 +1473,314 @@
     
-%7D%0A
     
-    return true;%0A
     %7D%0A
-%0A
+   
     
-public static void main(String%5B%5D args) %7B%0A        Problem479 prob = new Problem479();%0A        System.out.println(prob.largestPalindrome(1)); // 9%0A        System.out.println(prob.largestPalindrome(2)); // 987%0A        System.out.println(prob.largestPalindrome(3)); // 123%0A        System.out.println(prob.largestPalindrome(4)); // 597%0A        System.out.println(prob.largestPalindrome(5)); // 677%0A        System.out.println(prob.largestPalindrome(6)); // 1218%0A        System.out.println(prob.largestPalindrome(7)); // 877%0A        System.out.println(prob.largestPalindrome(8)); // 475
+     %7D%0A            maxSub--;%0A        %7D%0A    %7D%0A%0A    private static boolean isPalindrome(String str) %7B%0A        for (int i = 0, j = str.length() - 1; i %3C j; i++, j--) %7B%0A            if (str.charAt(i) != str.charAt(j)) %7B%0A                return false;%0A            %7D%0A        %7D%0A        return true;
 %0A   

Solve problem 479