fork download 
  1. import java.util.Arrays;
  2. import java.util.PriorityQueue;
  3.  
  4. public class Main {
  5.     /**
  6.      * combination of numbers
  7.      */
  8.     private static class Comb implements Comparable<Comb> {
  9.         public int nums[];
  10.         public int prod;
  11.  
  12.         public Comb(int[] nums) {
  13.             this.nums = Arrays.copyOf(nums, nums.length);
  14.             this.prod = 1;
  15.             for (int num : nums) {
  16.                 this.prod *= num;
  17.             }
  18.         }
  19.  
  20.         @Override
  21.         public int compareTo(Comb o) {
  22.             return o.prod - prod; // sort in descending order
  23.         }
  24.  
  25.         public boolean isPalindrome() {
  26.             String str = Integer.toString(prod);
  27.             return new StringBuilder(str).reverse().toString().equals(str);
  28.         }
  29.  
  30.         @Override
  31.         public String toString() {
  32.             return "Comb{" +
  33.                     "nums=" + Arrays.toString(nums) +
  34.                     ", prod=" + prod +
  35.                     '}';
  36.         }
  37.     }
  38.  
  39.     public static void main(String[] args) {
  40.         int n = 3;
  41.         int l = 3;
  42.         System.out.println("Biggest palindrome: " + getBiggestPalindrome(n, l));
  43.     }
  44.  
  45.     public static Comb getBiggestPalindrome(int n, int l) {
  46.         int minNum = (int) Math.pow(10, n - 1);
  47.         int maxNum = minNum * 10 - 1;
  48.         // create start combination
  49.         int[] startArr = new int[l];
  50.         Arrays.fill(startArr, maxNum);
  51.         Comb startComb = new Comb(startArr);
  52.         // iterate through combinations in descending order of its' products
  53.         PriorityQueue<Comb> q = new PriorityQueue<Comb>();
  54.         q.add(startComb);
  55.         while (!q.isEmpty()) {
  56.             // get combination with biggest product
  57.             Comb comb = q.poll();
  58.             // skip all combinations with same product
  59.             while (!q.isEmpty() && comb.prod == q.peek().prod) {
  60.                 q.poll();
  61.             }
  62.             // check if product is a palindrome
  63.             if (comb.isPalindrome()) {
  64.                 return comb;
  65.             }
  66.             // add dominated combinations of numbers
  67.             for (int i = 0; i < l; ++i) {
  68.                 if (comb.nums[i] > minNum) {
  69.                     // create new combination with decreased number in position `i`
  70.                     --comb.nums[i];
  71.                     Comb newComb = new Comb(comb.nums);
  72.                     ++comb.nums[i];
  73.                     // newComb.prod < comb.prod
  74.                     q.add(newComb);
  75.                 }
  76.             }
  77.         }
  78.         return null;
  79.     }
  80. }
Success #stdin #stdout 0.14s 320576KB
comments (?)
stdin 
Standard input is empty
stdout 
Biggest palindrome: Comb{nums=[989, 999, 979], prod=967262769}
https://ideone.com/ZSQC5d
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!