76 lines
1.6 KiB
C
76 lines
1.6 KiB
C
/* 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 (109)?*/
|
|
|
|
#define _POSIX_C_SOURCE 199309L
|
|
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <time.h>
|
|
|
|
#define N 1e9
|
|
|
|
int reverse(int n);
|
|
|
|
int main(int argc, char **argv)
|
|
{
|
|
int i, s, count = 0;
|
|
double elapsed;
|
|
struct timespec start, end;
|
|
|
|
clock_gettime(CLOCK_MONOTONIC, &start);
|
|
|
|
/* Brute force approach, sum each number and their reverse and
|
|
* check if there are only odd digits.*/
|
|
for(i = 11; i < N; i++)
|
|
{
|
|
if(i % 10 != 0)
|
|
{
|
|
s = i + reverse(i);
|
|
|
|
while(s > 0)
|
|
{
|
|
if((s % 10) % 2 == 0)
|
|
{
|
|
break;
|
|
}
|
|
s /= 10;
|
|
}
|
|
|
|
if(s == 0)
|
|
{
|
|
count++;
|
|
}
|
|
}
|
|
}
|
|
|
|
clock_gettime(CLOCK_MONOTONIC, &end);
|
|
|
|
elapsed = (end.tv_sec - start.tv_sec) + (double)(end.tv_nsec - start.tv_nsec) / 1000000000;
|
|
|
|
printf("Project Euler, Problem 145\n");
|
|
printf("Answer: %d\n", count);
|
|
|
|
printf("Elapsed time: %.9lf seconds\n", elapsed);
|
|
|
|
return 0;
|
|
}
|
|
|
|
int reverse(int n)
|
|
{
|
|
int reverse = 0;
|
|
|
|
while(n > 0)
|
|
{
|
|
reverse *= 10;
|
|
reverse += n % 10;
|
|
n /= 10;
|
|
}
|
|
|
|
return reverse;
|
|
}
|