Finding the largest palindrome product with Rust

The fourth Project Euler problem - Largest Palindrome Product - is stated as follows.

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99. Find the largest palindrome made from the product of two 3-digit numbers.

Pure brute-force with string conversions

fn is_palindrome(product: u32) -> bool {
    let str = product.to_string();
    let rev_str = str.chars().rev().collect::<String>();
    str == rev_str
}

fn get_largest_palindrome(n: u32) -> u32 {
    let start = 1 * u32::pow(10, n - 1);
    let end = start * 10;

    (start..end)
        .flat_map(|x| (x..end).map(move |y| x * y))
        .filter(|&p| is_palindrome(p))
        .max()
        .unwrap()
}

fn main() {
    println!(
        "Largest palindrome n=3: {}",
        get_largest_palindrome(3)
    );
}
N Execution Time Improvement
2 9.8 ms Baseline
3 933.5 ms Baseline
4 103286.6 ms Baseline

Pure brute-force with modulo operation

fn is_palindrome(n: u32, num: u32) -> bool {
    !(0..n).any(|a| (num / 10u32.pow(2 * n - 1 - a)) % 10 != (num / 10u32.pow(a)) % 10)
}

fn get_largest_palindrome(n: u32) -> u32 {
    let start = 1 * u32::pow(10, n - 1);
    let end = start * 10;

    (start..end)
        .flat_map(|x| (x..end).map(move |y| x * y))
        .filter(|&p| is_palindrome(n, p))
        .max()
        .unwrap()
}

fn main() {
    println!(
        "Largest palindrome n=3: {}",
        get_largest_palindrome(3)
    );
}
N Execution Time Improvement
2 1.4 ms 7X
3 104.8 ms 9X
4 10568.0 ms 10X

More efficient algorithm with string conversions

fn is_palindrome(product: u32) -> bool {
    let str = product.to_string();
    let rev_str = str.chars().rev().collect::<String>();
    str == rev_str
}

fn get_largest_palindrome(n: u32) -> u32 {
    let a_start = 10u32.pow(n - 1) / 11 + 1;
    let a_end = 10u32.pow(n) / 11 + 1;
    let b_start = 10u32.pow(n - 1);
    let b_end = 10u32.pow(n);

    (a_start..a_end)
        .flat_map(|x| (b_start..b_end).map(move |y| 11 * x * y))
        .filter(|&prod| prod > 10u32.pow(2 * n - 1) && is_palindrome(prod))
        .max()
        .unwrap()
}

fn main() {
    println!(
        "Largest palindrome n=3: {}",
        get_largest_palindrome(3)
    );
}
N Execution Time Improvement
2 1.3 ms 8X
3 125.8 ms 7X
4 14348.6 ms 7X

More efficient algorithm with modulo operation

fn is_palindrome(n: u32, num: u32) -> bool {
    !(0..n).any(|a| (num / 10u32.pow(2 * n - 1 - a)) % 10 != (num / 10u32.pow(a)) % 10)
}

fn get_largest_palindrome(n: u32) -> u32 {
    let a_start = 10u32.pow(n - 1) / 11 + 1;
    let a_end = 10u32.pow(n) / 11 + 1;
    let b_start = 10u32.pow(n - 1);
    let b_end = 10u32.pow(n);

    (a_start..a_end)
        .flat_map(|x| (b_start..b_end).map(move |y| 11 * x * y))
        .filter(|&prod| prod > 10u32.pow(2 * n - 1) && is_palindrome(n, prod))
        .max()
        .unwrap()
}

fn main() {
    println!(
        "Largest palindrome n=3: {}",
        get_largest_palindrome(3)
    );
}
N Execution Time Improvement
2 0.3 ms 30X
3 20.0 ms 47X
4 2149.2 ms 48X

The optimized versions of my pure brute-force algorithm is more or less a product of the friendly community over at the Rust Discrord. If you need help with the programming language Rust, I couldn’t recommend the Discord channel enough.