Skip to content

Instantly share code, notes, and snippets.

@realsba
Last active May 17, 2018 12:45
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save realsba/e89641d762db3b5cc0178afc3daa3d97 to your computer and use it in GitHub Desktop.
Find all palindromes made from the product of two 4-digit numbers
#include <iostream>
#include <iomanip>
#include <unordered_set>
#include <vector>
#include <fstream>
using Type = uint32_t;
using Magic = std::vector<Type>;
using Numbers = std::unordered_set<Type>;
Numbers palindromes;
Magic doMagic(int length)
{
Magic magic;
magic.emplace_back(0);
magic.emplace_back(1);
Type x = 1;
for (int i=1; i<length; ++i) {
x *= 10;
magic.emplace_back(x + 1);
}
return magic;
}
void calculate(Type x, int length, Type base)
{
const static auto magic = doMagic(10);
for (int i=0; i<=9; ++i) {
if (length > 2) {
calculate(x, length - 2, base * 10);
} else {
if (x % 10) palindromes.emplace(x);
}
x += (base * magic[length]);
}
}
int main(int argc, char** argv)
{
Type MIN=1000, MAX=9999;
calculate(0, 7, 1);
calculate(0, 8, 1);
std::ofstream os("output.txt");
for (Type a=MIN; a<=MAX; ++a) {
if (a % 10 == 0) continue;
for (Type b=a; b<=MAX; ++b) {
Type x = a * b;
Type l = x / 10000000;
if (l == 0) {
l = x / 1000000;
}
if (l == x % 10 && palindromes.count(x)) {
os << a << ' ' << b << ' ' << x << std::endl;
}
}
}
return 0;
}
@realsba
Copy link
Author

realsba commented May 17, 2018

Intel(R) Core(TM) i5-4300M CPU @ 2.60GHz, 16 GB RAM

real    0m0.220s
user    0m0.201s
sys     0m0.017s

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment