Problem 145 : How many reversible numbers are there below one-billion? (20%)

Description

original

Some positive integers n have the property that the sum [ n + reverse(n) ] consists entirely of odd (decimal) digits. For instance, 36 + 63 = 99 and 409 + 904 = 1313. We will call such numbers reversible; so 36, 63, 409, and 904 are reversible. Leading zeroes are not allowed in either n or reverse(n).

There are 120 reversible numbers below one-thousand.

How many reversible numbers are there below one-billion (10^9)?

간략해석

수와 그 수를 뒤집은 수를 더해서 모든 자리수가 홀수이면 그 수는 리버스수이다. (단, 수와 뒤집은 수의 시작은 0이 될 수 없다.)

$10^9$보다 작은 수들에 대하여 리버스 수의 개수는 몇 개인가?

Idea & Algorithm

naive idea

이 문제는 문제 조건대로 반복문으로 구현했더니 컴퓨터에서 3분 6초가 걸려 정답이 나왔다.

advanced idea

아직 더 나은 방법은 생각하지 못했다.

source code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const ll sz = 1e9;

int ans;

int main(){
  for(ll i = 1 ; i < sz ; i++){
    if(i%10==0) continue;
    ll j = i, rev = 0;
    while(j){
      rev = rev*10 + j%10;
      j /= 10;
    }
    rev += i;
    while(rev){
      if(rev%2==0) break;
      rev /= 10;
    }
    if(rev==0) ans ++;
  }
  cout << ans;
}

Problem 145