当前位置:首页 » Project Euler » 详细页

Palindromic sums 题号:125 难度: 25 中英对照

The palindromic number 595 is interesting because it can be written as the sum of consecutive squares: 62 + 72 + 82 + 92 + 102 + 112 + 122.

There are exactly eleven palindromes below one-thousand that can be written as consecutive square sums, and the sum of these palindromes is 4164. Note that 1 = 02 + 12 has not been included as this problem is concerned with the squares of positive integers.

Find the sum of all the numbers less than 108 that are both palindromic and can be written as the sum of consecutive squares.

Solution

此题很简单,可以用暴力法遍历求解 ​ 题中要求所有回文数的平方和小于 $10^8$,所以回文数肯定小于 $10000$,即从 $1 \sim 1000$ 遍历,然后依次加上其邻居点的平方和,判断该平方和是否是回文数,若是记录下来,否则继续迭代, 直到平方和大于上界 $10^8$。 代码中很详细直观,可直接查看。

Code

import java.util.HashSet;
import java.util.Set;


public class p125  {

    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }


    public static String run() {
        Set<Integer> nums = new HashSet<>();
        for (int i = 1; i <= 10000; i++) {
            int sum = i * i;
            for (int j = i + 1; ; j++) {
                sum += j * j;
                if (sum >= 100000000)
                    break;
                if (isPalindrome(sum))
                    nums.add(sum);
            }
        }

        long sum = 0;
        for (int x : nums)
            sum += x;
        return Long.toString(sum);
    }

    // Returns the reverse of the given string.
    public static String reverse(String s) {
        return new StringBuilder(s).reverse().toString();
    }


    // Tests whether the given string is a palindrome.
    public static boolean isPalindrome(String s) {
        return s.equals(reverse(s));
    }


    // Tests whether the given integer is a palindrome in decimal (base 10).
    public static boolean isPalindrome(int x) {
        return isPalindrome(Integer.toString(x));
    }
}
2906969179
50ms