Optimization of the largest palindrome from a product of two three-digit numbers?

Question

I am working on an interview question that I was asked in which I had to write a program to find the largest palindrome from a product of two three-digit numbers.

Here is the question

I came up with this brute force approach that starts from the bottom.

public class LargestPalindromeQuestion { public static void main(String[] args) { int value = 0; for (int i = 100; i <= 999; i++) { for (int j = i; j <= 999; j++) { int value1 = i * j; if (isPalindrome(value1) && value < value1) { value = value1; } } } System.out.println(value); } private static boolean isPalindrome(final int product) { int p = product; int reverse = 0; while (p != 0) { reverse *= 10; reverse += p % 10; p /= 10; } return reverse == product; } } 

They asked me what kind of optimizations can I do in this program? I mentioned that we can try to crop the search space and optimize the check step for each element in the search space, but then I am embarrassed, how would this work in my solution above?

What optimizations can we do in this program? He is now performing steps 810000 to find the largest palindrome.

What is the minimum number of steps we can take to find the largest palindrome in two three-digit numbers?

Answer 1

The program looks very good to me. I would make the number of cycles i from 999 to 100 , and I would only check the values ​​of j , which would actually give a larger product than the current maximum.

This program may end unexpectedly in the near future, with i == 952 , to be precise. The mathematical reason for this is that as soon as the solution 906609 ( 993 * 913 ) is found, it will no longer be possible to find a larger palindrome, where the larger coefficient is less than the square root of 906609 , which is 952.160...

 public static void main(String[] args) { int value = 0; for (int i = 999; i >= 100; i--) { int r = value / i; if (r >= i) { System.out.println("We broke at i = " + i); break; } for (int j = i; j > r; j--) { int value1 = i * j; if (isPalindrome(value1)) { value = value1; break; } } } System.out.println(value); } 

Answer 2

One fairly simple way to optimize this would be to simply start with the highest 3-digit numbers instead of the smallest ones. Since the solution is likely to be closer to the pair (999, 999) than to (100, 100).

Answer 3

One useful mechanism for trimming the search tree is to notice that the highest digit of the product a * b does not change often. For instance.

 a = 111; b = 112 a*b = 12432 ; b = 113 a*b = 12543 ; b = 114 a*b = 12654 ; ... ; b = 180 a*b = 19980 ; b = 181 a*b = 20091 = (19980 + a) 

Thus, for all values ​​between (a = 111, a <b <181), the MSB is already known, which should be equal to LSB or (a% 10) * (b% 10)% 10 == MSB.

  eg LSB = 1 --> a % 10 == 1, b % 10 == 1 OR a % 10 == 3, b % 10 == 7 OR a % 10 == 7, b % 10 == 3 OR a % 10 == 9, b % 10 == 9 

In most cases, it either does not exist, or only one candidate in the set 'b' should be checked for any MSB pair,% 10.

Answer 4

The smallest number of steps that I could get is 375. Consider multiplying the three-digit number a1a2a3 by the three-digit number, b1b2b3 :

JavaScript Code:

 var modHash = new Array(10); var iterations = 0; for (var i=1; i<10; i++){ modHash[i] = {0: [0]} for (var j=1; j<10; j++){ iterations ++; var r = i * j % 10; if (modHash[i][r]) modHash[i][r].push(j); else modHash[i][r] = [j]; } } var highest = 0; function multiples(x,y,carry,mod){ for (var i in modHash[x]){ var m = (10 + mod - i - carry) % 10; if (modHash[y][m]){ for (var j in modHash[x][i]){ for (var k in modHash[y][m]){ iterations ++; var palindrome = num(9,modHash[y][m][k],x,9,modHash[x][i][k],y); if (x == 3 && mod == 0){ console.log(x + " * " + modHash[x][i][j] + " + " + y + " * " + modHash[y][m][k] + ": " + palindrome); } var str = String(palindrome); if (str == str.split("").reverse().join("") && palindrome > highest){ highest = palindrome; } } } } } } function num(a1,a2,a3,b1,b2,b3){ return (100*a1 + 10*a2 + a3) * (100*b1 + 10*b2 + b3); } var a3b3s = [[7,7,4],[9,1,0],[3,3,0]]; for (var i in a3b3s){ for (var mod=0; mod<10; mod++){ var x = a3b3s[i][0], y = a3b3s[i][1], carry = a3b3s[i][2]; multiples(x,y,carry,mod); } } console.log(highest); console.log("iterations: " + iterations); 

Conclusion:

 3 * 0 + 3 * 0: 815409 3 * 7 + 3 * 3: 907809 3 * 4 + 3 * 6: 908109 3 * 1 + 3 * 9: 906609 3 * 8 + 3 * 2: 907309 3 * 5 + 3 * 5: 908209 3 * 2 + 3 * 8: 907309 3 * 9 + 3 * 1: 906609 3 * 6 + 3 * 4: 908109 3 * 3 + 3 * 7: 907809 906609 iterations: 375 

Answer 5

Optimize isPalindrome first by dividing 6 digits by 3 digits. that is, N = ABCDEF => a = ABC = N / 1000, b = DEF = N% 1000; Then cancel b and return == reverseed_b;

Secondly, when creating palindromes, the loop is up to max_palindrome_so_far / 999, which is the minimum value that you will use. max_palindrome_so_far is initially N.

 public class Solution { public static boolean isPalindrome(int n){ int a = n/1000; int b = n%1000; int d, r = 0, i = 3; while(i-- > 0){ d = b%10; r = r*10 + d; b = b/10; } if (a == r) return true; return false; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); for(int a0 = 0; a0 < t; a0++){ int n = in.nextInt(); int r=0, m=n; int i,j; for(i = 999;i>=100;i--){ for(j = 999;j>=m/999;j--){ if (i*j < n && i*j > 100000 && isPalindrome(i*j)){ r = Math.max(i*j, r); m = r; } } } // System.out.println(i + " * " + j + " = " + i*j); System.out.println(r); } } }