<< problem 611 - Hallway of square steps | Pythagorean Ant - problem 613 >> |
Problem 612: Friend numbers
(see projecteuler.net/problem=612)
Let's call two numbers friend numbers if their representation in base 10 has at least one common digit.
E.g. 1123 and 3981 are friend numbers.
Let f(n) be the number of pairs (p,q) with 1 <= p < q < n such that p and q are friend numbers.
f(100)=1539
Find f(10^18) mod 1000267129.
Not solved yet
My code works for the "small" example but can't find the solution to the "big" problem.
What I've Done So Far
I came up with two brute force algorithms. Given enough time they could solve the problem - but you should be ready to wait a few years until you see the result ...
Both algorithms rely on the function fingerprint
with returns a bitmask: if its parameter x
contains the digit n
at least once, then the n-th bit of the result is set.
For example fingerprint(1305)
is 00101011
in binary (or 43 decimal) and fingerprint(52)
is 00100100
in binary (= 36 in decimal).
If two numbers are friend numbers then their fingerprints share at least one bit and (fingerprint(a) & fingerprint(b)) != 0
. Note: it's a single &
because it's the binary AND, not the logical AND.
Let's check whether 1305 and 52 are friends numbers:
(fingerprint(1305) & fingerprint(52)) = 00101011b & 00100100b = 00100000b != 0
→ yes, they are friend numbers
The first algorithm bruteForce
is an implementation of the obvious O(n^2) strategy:
compare each number q
with all smaller numbers p
.
It takes about 0.5 seconds to solve f(10^4) and 50 seconds to solve f(10^5).
Runtime for f(10^n) seems to be approximately dfrac{10^{2n}}{2 * 10^8} seconds. So f(10^18) needs approx 5 * 10^27 seconds which is 10^10 longer than the universe existed. Oops.
A significant speed-up can be achieved if switching from that basic O(n^2) algorithm to a slightly smarter O(n) algorithm:
- there are 10 different digits in the decimal system, so we have at most 2^10 different bitmasks (actually it's 2^10 - 1 because every numbers has at least one digit but let's ignore that)
- I need to keep track of 2^10 running counters: how often each bitmask was found so far
- for each number: add all counters whose associated bitmask
i
is "compatible" to the current numbers bitmask - "compatible" means that a counter's bitmask
i
shares at least one bit withfingerprint(current)
Runtime for f(10^n) seems to be approximately 10^n * 10^-6 seconds. So f(10^18) needs approx 10^12 seconds which is close to 110000 years.
It's getting late now and I'm too sleepy to figure out a proper way to solve that problem ...
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 | ./612
Output:
Note: the original problem's input 1000000000000000000
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. Or just jump to my GitHub repository.
#include <iostream>
// taken from problem statement
const unsigned int Modulo = 1000267129;
// set the n-th bit if x contains digit n
unsigned int fingerprint(unsigned long long x)
{
unsigned int result = 0;
while (x > 0)
{
auto digit = x % 10;
result |= 1 << digit;
x /= 10;
}
return result;
}
// O(n^2) algorithm, compare each number q with all smaller numbers p
unsigned long long bruteForce(unsigned long long limit)
{
unsigned long long result = 0;
for (unsigned long long q = 1; q < limit; q++)
{
// bitmask of used digits
auto maskQ = fingerprint(q);
for (unsigned long long p = 1; p < q; p++)
{
auto maskP = fingerprint(p);
// share at least one digit
if ((maskQ & maskP) != 0)
{
result++;
// much faster than %-operator
if (result == Modulo)
result = 0;
}
}
}
return result;
}
// O(n) algorithm, much faster than bruteForce() but still too slow to handle limit = 10^18
// but still useful up to 10^8
unsigned long long slow(unsigned long long limit)
{
unsigned long long result = 0;
// setup counters for each bitmask (10 digits => 2^10 bitmasks
const auto NumCounters = 1 << 10;
unsigned long long maskCount[NumCounters] = { 0 };
// iterate over all numbers
for (unsigned long long q = 1; q < limit; q++)
{
// get current bitmask
auto maskQ = fingerprint(q);
// add all counters that share at least one bit with the current bitmask
for (auto i = 1; i < NumCounters; i++)
if (i & maskQ)
{
result += maskCount[i];
if (result >= Modulo)
result %= Modulo;
}
// add current number to its bitmask counter
maskCount[maskQ]++;
// avoid overflows
if (maskCount[maskQ] == Modulo)
maskCount[maskQ] = 0;
}
return result;
}
int main()
{
// friends( 100) = 1539
// friends( 1000) = 289665
// friends( 10000) = 39235977
// friends( 100000) = 4528635021 % 1000267129 = 527566505
// friends(1000000) = 481858831665 % 1000267129 = 730342616
// friends( 10^7) = 49369806187101 % 1000267129 = 621768177
// friends( 10^8) = 4979780329300065 % 1000267129 = 440930015
unsigned long long limit = 1000000ULL;
std::cin >> limit;
//std::cout << bruteForce(limit) << std::endl;
std::cout << slow(limit) << std::endl;
return 0;
}
This solution contains 12 empty lines, 22 comments and 1 preprocessor command.
Changelog
December 14, 2017 solve up to 10^8
Links
projecteuler.net/thread=612 - the best forum on the subject (note: you have to submit the correct solution first)
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 | |
[new] | the flashing problem is the one I solved most recently |
I stopped working on Project Euler problems around the time they released 617.
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 | 612 | 613 | 614 | 615 | 616 | 617 | 618 | 619 | 620 | 621 | 622 | 623 | 624 | 625 |
626 | 627 | 628 | 629 | 630 | 631 | 632 | 633 | 634 | 635 | 636 | 637 | 638 | 639 | 640 | 641 | 642 | 643 | 644 | 645 | 646 | 647 | 648 | 649 | 650 |
651 | 652 | 653 | 654 | 655 | 656 | 657 | 658 | 659 | 660 | 661 | 662 | 663 | 664 | 665 | 666 | 667 | 668 | 669 | 670 | 671 | 672 | 673 | 674 | 675 |
676 | 677 | 678 | 679 | 680 | 681 | 682 | 683 | 684 | 685 | 686 | 687 | 688 | 689 | 690 | 691 | 692 | 693 | 694 | 695 | 696 | 697 | 698 | 699 | 700 |
701 | 702 | 703 | 704 | 705 | 706 | 707 | 708 | 709 | 710 | 711 |
I scored 13526 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 611 - Hallway of square steps | Pythagorean Ant - problem 613 >> |