Optymalizowanie największego palindromu z iloczynu dwóch liczb trzycyfrowych?

Question

Pracuję nad pytaniem do wywiadu, w którym zostałem poproszony, w którym mam napisać program do znalezienia największego palindromu z iloczynu dwóch liczb trzycyfrowych.

Oto question

wymyśliłem tej metody brute force, która rozpoczyna się od dołu.

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

Zapytano mnie, jakie są optymalizacje, które mogę wykonać w tym programie? Wspomniałem, że możemy próbować przycinać przestrzeń poszukiwań i optymalizować krok sprawdzania każdego elementu w przestrzeni wyszukiwania, ale jestem zdezorientowany, w jaki sposób sprawiłbym, że działałoby to w powyższym rozwiązaniu?

Jakie są optymalizacje, które możemy wykonać w tym programie? W tej chwili wykonuje on 810000 kroków, aby znaleźć największy palindrom.

Jaka jest najmniejsza liczba kroków, które możemy wykonać, aby znaleźć największy palindrom w dwóch trzycyfrowych liczbach?

Answer 1

Jednym z dość prostych sposobów optymalizacji byłoby rozpoczęcie od najwyższych 3-cyfrowych liczb zamiast najmniejszych. Ponieważ rozwiązanie będzie najprawdopodobniej bliżej pary (999, 999) niż do (100, 100).

Answer 2

Program wygląda bardzo dobrze. Sprawiłbym, że liczba pętli i spadła z 999 do 100, a ja sprawdziłbym tylko wartości j, które faktycznie dawałyby większy produkt niż bieżące maksimum.

Ten program może zakończyć się niespodziewanie wkrótce, pod numerem telefonu i == 952. Matematyczna przyczyna tego jest taka, że ​​po znalezieniu rozwiązania nie można już znaleźć większego palindromu, gdzie większy współczynnik jest mniejszy niż pierwiastek kwadratowy z 906609, który jest 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 3

Jeden przydatny mechanizm przycinać drzewa przeszukiwania jest, aby zauważyć, że najwyższa cyfra produktu a * b nie zmienia się często. Na przykład.

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) 

Tak więc, wszystkie wartości pośrednie (A = 111, < b < 181), jeden zna już MSB, która musi być równa do wartości LSB lub (o stężeniu 10%) * (b% 10)% 10 == MSB.

e.g. 
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 

Przez większość czasu nie ma ani żaden lub tylko jeden kandydat w zestawie „B”, które należy sprawdzić dla dowolnej pary MSB, w% 10.

Answer 4

Najmniej liczba kroków mogę dostać się jest 375. Rozważmy pomnożenie liczby trzycyfrowe, a1a2a3, przez liczbę trzycyfrową, b1b2b3:

kod

JavaScript:

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

wyjściowa:

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

Pierwsza optymalizacja toPalindrom, dzieląc 6 cyfr na 3 cyfry. to znaczyN = ABCDEF => a = ABC = N/1000, b = DEF = N% 1000; Następnie odwróć b i zwróć a == odwrócone_b;

Po drugie podczas produkcji pętli palindromów aż do max_palindrome_so_far/999, która jest minimalną wartością, której można użyć. max_palindrome_so_far jest początkowo równa 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); 
     } 
    } 
}