Table of Contents
1 Problem
The decimal number, 585 = \(1001001001_2\) (binary), is palindromic in both bases.
Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.
(Please note that the palindromic number, in either base, may not include leading zeros.)
2 Solution
2.1 Brute Force
因为任何进制数字开头不能为0,则二进制表示时最低位必为1,故数字必为奇数.
接下来只要对所有范围内的奇数进行回文数检查即可.
检查方法:
- 将数字每位分解,相应位对比是否相同(121,第一位和第三位比较)
- 将数字倒过来写,比较与原数是否相等(123,反过来即321不等)
主要利用整除与模,类似于进制间的转换
2.2 Generate
直接在范围内产生要求的二进制回文数,再检查是否为十进制的回文数.检查方法同 Brute Force
每个数可生成两个回文数: 01 -> 0110 or 010
具体操作主要用整除与模,对于二进制来说则有更快捷的shift等位操作.
3 Answer
872187
Source:C++