読者です 読者をやめる 読者になる 読者になる

Project Euler 36

Problem 36

  • 2 進数の回文は、末尾が必ず 1 となるので、奇数のみ調べる。
using System;
using System.Collections.Generic;
using System.Linq;

class PE036 {
    static string Bin(int n) {
        if (n < 0) throw new Exception("n < 0");
        
        var ls = new List<char>();
        if (n == 0) ls.Add('0');
        while (n > 0) {
            ls.Add((char)((n % 2) + '0'));
            n /= 2;
        }
        ls.Reverse();
        return new string(ls.ToArray());
    }
    
    static bool IsPalindrome(string s) {
        int n = s.Length/2;
        for (int i = 0; i < n; i++) {
            if (s[i] != s[s.Length-i-1])
                return false;
        }
        return true;
    }
    
    static void Main() {
        int ans = 0;
        for (int i = 1; i < 1000000; i += 2) {
            if (IsPalindrome(i.ToString()) && IsPalindrome(Bin(i))) {
                ans += i;
            }
        }
        Console.WriteLine(ans);
    }
}

以下、メモ。

  • 回文かどうかを調べるのではなくて、回文を作るのはどうか。たとえば、12 があるとして、これを反転させたものと結合させると、1221 になり、回文となる。