<< problem 301 - Nim | Primonacci - problem 304 >> |
Problem 303: Multiples with small digits
(see projecteuler.net/problem=303)
For a positive integer n, define f(n) as the least positive multiple of n that, written in base 10, uses only digits <= 2.
Thus f(2)=2, f(3)=12, f(7)=21, f(42)=210, f(89)=1121222.
Also, sum_{n=1..100}{dfrac{f(n)}{n}} = 11363107.
Find sum_{n=1..10000}{dfrac{f(n)}{n}}.
My Algorithm
Initially I create all positive numbers with one digits that is <= 2 → zeroOneTwo = { 1, 2 }
.
Then each number between 1 and 10000 (see open
) is checked whether it divides any of the numbers in zeroOneTwo
.
The next iteration appends to each value in zeroOneTwo
the digits 0, 1 and 2.
That means, { 1, 2 }
→ { 10, 11, 12, 20, 21, 22 }
.
zeroOneTwo
grows pretty fast: it contains 2 * 3^{digits-1} elements.
Unfortunately, 11112222222222222222 is the smallest multiple of 9999.
My algorithm would need to allocate enough memory to store 2 * 3^{20-1} approx 2.3 * 10^9 values.
Even worse, it would be pretty slow.
When looking at the multiples of each number, I discovered that numbers where the last digit 9 have large multiples.
Especially large are the multiples when all digits are 9s.
My program easily found the multiples of 9, 99 and 999 and a certain pattern became apparent:
their smallest multiple is a sequence of n ones and 4n twos where n is the number of nines.
You will see that my code precomputes the result for 9999.
Another optimization (see #ifdef FAST999
) is to make use of the pattern of multiples of 999:
there are alway three 1s and twelve 2s, except 5*999 and 10*999 which have a trailing zero on top.
If you disable that optimization then the program will be about half as fast but needs four times more memory.
Alternative Approaches
Heavy use of std::next_permutation
and/or base-3 arithmetic could eliminate the need for my zeroOneTwo
container
(responsible for the "high" memory consumption) but it seems that performance would suffer significantly.
Note
My first attempt was based Dynamic Programming but I could make the program fast enough.
Interactive test
You can submit your own input to my program and it will be instantly processed at my server:
This is equivalent toecho 100 | ./303
Output:
Note: the original problem's input 10000
cannot be entered
because just copying results is a soft skill reserved for idiots.
(this interactive test is still under development, computations will be aborted after one second)
My code
… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
// see explanation
#define FAST999
int main()
{
unsigned int limit = 10000;
std::cin >> limit;
unsigned long long sum = 0;
// put all numbers 1..10000 in "open"
std::vector<unsigned int> open;
for (unsigned int i = 1; i <= limit; i++)
open.push_back(i);
// repeated 9s follow a certain pattern ... pre-compute them
if (limit >= 9999)
{
sum += 11112222222222222222ULL / 9999;
open.erase(open.begin() + 9999 - 1);
// zero-based index but first element is one, therefore subtract one
}
// special treatment for multiples of 999 (saves memory and makes program faster)
// three 1s, twelve 2s and potentially a trailing zero
#ifdef FAST999
for (unsigned int factor = 10; factor >= 1; factor--)
{
unsigned int current = factor * 999;
if (current > limit)
continue;
// try every permutation of these digits ...
std::string tripleNine = "111222222222222";
do
{
unsigned long long multiple = std::stol(tripleNine);
// 4995 (5*999) and 9990 (10*999) require a trailing zero, too
if (factor % 5 == 0)
multiple *= 10;
// divisible ?
if (multiple % current == 0)
{
// yes, resolved one more number
sum += multiple / current;
open.erase(open.begin() + current - 1);
break;
}
} while (std::next_permutation(tripleNine.begin(), tripleNine.end()));
}
#endif
// all positive numbers of length 1 with digits <= 2
std::vector<unsigned long long> zeroOneTwo = { 1, 2 };
// until a divisor is found for all numbers
while (!open.empty())
{
// numbers where still no divisor was found
std::vector<unsigned int> next;
// look at all unresolved numbers
for (auto current : open)
{
bool lastMustBeZero = current % 5 == 0;
bool found = false;
// check whether any number with digits <= 2 can be divided by it
for (auto multiple : zeroOneTwo)
{
if (lastMustBeZero)
multiple *= 10;
if (multiple % current == 0)
{
// yes, resolved one more number
sum += multiple / current;
found = true;
break;
}
}
// no match found, must look at numbers with one more digit, too
if (!found)
next.push_back(current);
}
// prepare next iteration
open = std::move(next);
if (!open.empty())
{
// append a zero, a one and a two to each number
std::vector<unsigned long long> longer;
for (auto multiple : zeroOneTwo)
{
longer.push_back(multiple * 10);
longer.push_back(multiple * 10 + 1);
longer.push_back(multiple * 10 + 2);
}
zeroOneTwo = std::move(longer);
}
}
// display result
std::cout << sum << std::endl;
return 0;
}
This solution contains 16 empty lines, 20 comments and 7 preprocessor commands.
Benchmark
The correct solution to the original Project Euler problem was found in 0.6 seconds on an Intel® Core™ i7-2600K CPU @ 3.40GHz.
Peak memory usage was about 46 MByte.
(compiled for x86_64 / Linux, GCC flags: -O3 -march=native -fno-exceptions -fno-rtti -std=gnu++11 -DORIGINAL
)
See here for a comparison of all solutions.
Note: interactive tests run on a weaker (=slower) computer. Some interactive tests are compiled without -DORIGINAL
.
Changelog
July 3, 2017 submitted solution
July 3, 2017 added comments
Difficulty
Project Euler ranks this problem at 35% (out of 100%).
Links
projecteuler.net/thread=303 - the best forum on the subject (note: you have to submit the correct solution first)
Code in various languages:
Python github.com/Meng-Gen/ProjectEuler/blob/master/303.py (written by Meng-Gen Tsai)
Python github.com/nayuki/Project-Euler-solutions/blob/master/python/p303.py (written by Nayuki)
Python github.com/smacke/project-euler/blob/master/cpp/303.py (written by Stephen Macke)
C++ github.com/evilmucedin/project-euler/blob/master/euler303/euler303/euler303.cpp (written by Den Raskovalov)
C++ github.com/roosephu/project-euler/blob/master/303.cpp (written by Yuping Luo)
Java github.com/nayuki/Project-Euler-solutions/blob/master/java/p303.java (written by Nayuki)
Java github.com/thrap/project-euler/blob/master/src/Java/Problem303.java (written by Magnus Solheim Thrap)
Mathematica github.com/steve98654/ProjectEuler/blob/master/303.nb
Those links are just an unordered selection of source code I found with a semi-automatic search script on Google/Bing/GitHub/whatever.
You will probably stumble upon better solutions when searching on your own. Maybe not all linked resources produce the correct result and/or exceed time/memory limits.
Heatmap
Please click on a problem's number to open my solution to that problem:
green | solutions solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too | |
yellow | solutions score less than 100% at Hackerrank (but still solve the original problem easily) | |
gray | problems are already solved but I haven't published my solution yet | |
blue | solutions are relevant for Project Euler only: there wasn't a Hackerrank version of it (at the time I solved it) or it differed too much | |
orange | problems are solved but exceed the time limit of one minute or the memory limit of 256 MByte | |
red | problems are not solved yet but I wrote a simulation to approximate the result or verified at least the given example - usually I sketched a few ideas, too | |
black | problems are solved but access to the solution is blocked for a few days until the next problem is published | |
the flashing problem is the one I solved most recently |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 |
51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 |
76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 |
101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 |
126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 |
151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 |
176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 | 194 | 195 | 196 | 197 | 198 | 199 | 200 |
201 | 202 | 203 | 204 | 205 | 206 | 207 | 208 | 209 | 210 | 211 | 212 | 213 | 214 | 215 | 216 | 217 | 218 | 219 | 220 | 221 | 222 | 223 | 224 | 225 |
226 | 227 | 228 | 229 | 230 | 231 | 232 | 233 | 234 | 235 | 236 | 237 | 238 | 239 | 240 | 241 | 242 | 243 | 244 | 245 | 246 | 247 | 248 | 249 | 250 |
251 | 252 | 253 | 254 | 255 | 256 | 257 | 258 | 259 | 260 | 261 | 262 | 263 | 264 | 265 | 266 | 267 | 268 | 269 | 270 | 271 | 272 | 273 | 274 | 275 |
276 | 277 | 278 | 279 | 280 | 281 | 282 | 283 | 284 | 285 | 286 | 287 | 288 | 289 | 290 | 291 | 292 | 293 | 294 | 295 | 296 | 297 | 298 | 299 | 300 |
301 | 302 | 303 | 304 | 305 | 306 | 307 | 308 | 309 | 310 | 311 | 312 | 313 | 314 | 315 | 316 | 317 | 318 | 319 | 320 | 321 | 322 | 323 | 324 | 325 |
326 | 327 | 328 | 329 | 330 | 331 | 332 | 333 | 334 | 335 | 336 | 337 | 338 | 339 | 340 | 341 | 342 | 343 | 344 | 345 | 346 | 347 | 348 | 349 | 350 |
351 | 352 | 353 | 354 | 355 | 356 | 357 | 358 | 359 | 360 | 361 | 362 | 363 | 364 | 365 | 366 | 367 | 368 | 369 | 370 | 371 | 372 | 373 | 374 | 375 |
376 | 377 | 378 | 379 | 380 | 381 | 382 | 383 | 384 | 385 | 386 | 387 | 388 | 389 | 390 | 391 | 392 | 393 | 394 | 395 | 396 | 397 | 398 | 399 | 400 |
401 | 402 | 403 | 404 | 405 | 406 | 407 | 408 | 409 | 410 | 411 | 412 | 413 | 414 | 415 | 416 | 417 | 418 | 419 | 420 | 421 | 422 | 423 | 424 | 425 |
426 | 427 | 428 | 429 | 430 | 431 | 432 | 433 | 434 | 435 | 436 | 437 | 438 | 439 | 440 | 441 | 442 | 443 | 444 | 445 | 446 | 447 | 448 | 449 | 450 |
451 | 452 | 453 | 454 | 455 | 456 | 457 | 458 | 459 | 460 | 461 | 462 | 463 | 464 | 465 | 466 | 467 | 468 | 469 | 470 | 471 | 472 | 473 | 474 | 475 |
476 | 477 | 478 | 479 | 480 | 481 | 482 | 483 | 484 | 485 | 486 | 487 | 488 | 489 | 490 | 491 | 492 | 493 | 494 | 495 | 496 | 497 | 498 | 499 | 500 |
501 | 502 | 503 | 504 | 505 | 506 | 507 | 508 | 509 | 510 | 511 | 512 | 513 | 514 | 515 | 516 | 517 | 518 | 519 | 520 | 521 | 522 | 523 | 524 | 525 |
526 | 527 | 528 | 529 | 530 | 531 | 532 | 533 | 534 | 535 | 536 | 537 | 538 | 539 | 540 | 541 | 542 | 543 | 544 | 545 | 546 | 547 | 548 | 549 | 550 |
551 | 552 | 553 | 554 | 555 | 556 | 557 | 558 | 559 | 560 | 561 | 562 | 563 | 564 | 565 | 566 | 567 | 568 | 569 | 570 | 571 | 572 | 573 | 574 | 575 |
576 | 577 | 578 | 579 | 580 | 581 | 582 | 583 | 584 | 585 | 586 | 587 | 588 | 589 | 590 | 591 | 592 | 593 | 594 | 595 | 596 | 597 | 598 | 599 | 600 |
601 | 602 | 603 | 604 | 605 | 606 | 607 | 608 | 609 | 610 | 611 |
I scored 13,486 points (out of 15700 possible points, top rank was 17 out of ≈60000 in August 2017) at Hackerrank's Project Euler+.
My username at Project Euler is stephanbrumme while it's stbrumme at Hackerrank.
Look at my progress and performance pages to get more details.
Copyright
I hope you enjoy my code and learn something - or give me feedback how I can improve my solutions.
All of my solutions can be used for any purpose and I am in no way liable for any damages caused.
You can even remove my name and claim it's yours. But then you shall burn in hell.
The problems and most of the problems' images were created by Project Euler.
Thanks for all their endless effort !!!
<< problem 301 - Nim | Primonacci - problem 304 >> |