<< problem 103 - Special subset sums: optimum | Special subset sums: testing - problem 105 >> |

# Problem 104: Pandigital Fibonacci ends

(see projecteuler.net/problem=104)

The Fibonacci sequence is defined by the recurrence relation:

F_n = F_{n-1} + F_{n-2}, where F_1 = 1 and F_2 = 1.

It turns out that F_541, which contains 113 digits, is the first Fibonacci number for which the last nine digits are 1-9 pandigital (contain all the digits 1 to 9, but not necessarily in order).

And F_2749, which contains 575 digits, is the first Fibonacci number for which the first nine digits are 1-9 pandigital.

Given that F_k is the first Fibonacci number for which the first nine digits AND the last nine digits are 1-9 pandigital, find k.

# My Algorithm

My solution is based on a stripped down version of my `BigNum`

class and stores 9 digits per cell, that's why it's called `BillionNum`

(because `MaxDigit = 1000000000`

→ 10^9).

It only supports `operator+=`

.

`isPandigital(x, digits)`

returns true if `x`

is `1..digits`

-pandigital, e.g. `isPandigital(312, 3) == true`

because 312 is 3-pandigital.

The original problem assumes `digits = 9`

.

`x`

's digits are chopped off step-by-step and a bitmask tracks which digits we have already seen.

Zero is not part of any pandigital number, not even implicit leading zeros.

The `main`

routines analyzes the lower digits first.

Only when they are pandigital then the highest digits are checked, too, because that's bit slower:

I take all digits from the highest cell of my `BillionNum`

. If there are too few digits, all digits in its neighboring cell are included.

We might have too many digits now, therefore I remove the lowest digit until the number of digits is correct.

If these digits are pandigital, then we are done.

Finding the next Fibonacci number involves `operator+=`

of `BillionNum`

. The default algorithm is:

F_{next} = F_a + F_b

F_a = F_b

F_b = F_{next}

→ quite a few memory allocations, and many object constructor/destruction will take place behind the curtain.

A simple trick to improve performance is to use these equations instead, which get rid of these "memory/object bookkeeping" effects:

F_a += F_b (add in-place)

F_a <=> F_b (swap contents of both object, which is technically just swapping two pointers)

The main performance boost comes from my next trick:

- we check the lowest digit whether they are pandigital

- we check the highest digit whether they are pandigital

- *but we don't care what the other digits are*

→ whenever a number exceeds a certain size, I delete digits from the middle

Currently I delete if there are more than 10 cells, which represent 9 x 10 = 90 digits.

There is no special reason why I chose 10, it was the first number that I tried and it worked immediately.

The solution is found 100x faster now ...

## Modifications by HackerRank

The user can define F_1 and F_2 as well as how many digits should be pandigital.

# My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too.

The code contains `#ifdef`

s to switch between the original problem and the Hackerrank version.

Enable `#ifdef ORIGINAL`

to produce the result for the original problem (default setting for most problems).

#include <iostream>
#include <vector>
//#define ORIGINAL

// store single digits with lowest digits first
// e.g. 1024 is stored as { 4,2,0,1 }

struct BillionNum : public std::vector<unsigned int>
{
// must store exactly 9 digits per cell
static const unsigned int MaxDigit = 1000000000;
// fill one cell
BillionNum(unsigned int x)
{
push_back(x);
}
// add a big number
void operator+=(const BillionNum& other)
{
// this code is a 95% copy of my BigNum class
// add in-place, make sure it's big enough
if (size() < other.size())
resize(other.size(), 0);
unsigned int carry = 0;
for (size_t i = 0; i < size(); i++)
{
// perform standard addition algorithm
carry += operator[](i);
if (i < other.size())
carry += other[i];
else
if (carry == 0)
return;
if (carry < MaxDigit)
{
// no overflow
operator[](i) = carry;
carry = 0;
}
else
{
// yes, we have an overflow
operator[](i) = carry - MaxDigit;
carry = 1;
}
}
if (carry > 0)
push_back(carry);
}
};
// return true if x is pandigital (1..digits)

bool isPandigital(unsigned int x, unsigned int digits = 9)
{
unsigned int mask = 0; // zero is not allowed, only 1 to 9
for (unsigned int i = 0; i < digits; i++)
{
// get next digit
auto current = x % 10;
if (current == 0 || current > digits)
return false;
auto bit = 1 << current;
// already seen ?
if ((mask & bit) != 0)
return false;
// mark that digit as "used"
mask |= bit;
x /= 10;
}
return true;
}
int main()
{
unsigned int first = 1; // F_1 = 1
unsigned int second = 1; // F_2 = 1
unsigned int digits = 9; // 9-pandigital (1..9)
#ifndef ORIGINAL
std::cin >> first >> second >> digits;
#endif
if (first == 1 && digits == 1)
{
std::cout << "1" << std::endl;
return 0;
}
unsigned long long Modulo = 1; // 10^digits
for (unsigned i = 1; i <= digits; i++)
Modulo *= 10;
// convert to a simplified BigNum
BillionNum a = first;
BillionNum b = second;
for (unsigned int i = 2; i <= 2000000; i++)
{
// analyze the lowest digits
auto lowest = b.front() % Modulo;
bool isPanLow = isPandigital(lowest, digits);
// look at the highest digits
if (isPanLow)
{
unsigned long long highest = b.back();
// maybe too few digits: use next cells, too
if (highest < Modulo && b.size() > 1)
highest = highest * BillionNum::MaxDigit + b[b.size() - 2];
// too many digits ? shrink until we have the right number of digits
while (highest >= Modulo)
highest /= 10;
// check if pandigital
if (isPandigital(highest, digits))
{
// yes, pandigital on both ends !
std::cout << i << std::endl;
return 0;
}
}
// next Fibonacci number
a += b;
std::swap(a, b);
// don't compute all digits:
// - look at the lowest digits
// - and look at the highest (incl. some of its neighbors because of carry)
// => remove those in the middle
// => my "magic numbers" 10 and 2 were chosen pretty much at random ...
if (a.size() > 10)
{
a.erase(a.begin() + 2);
b.erase(b.begin() + 2);
}
}
// failed
std::cout << "no solution" << std::endl;
return 0;
}

This solution contains 24 empty lines, 29 comments and 4 preprocessor commands.

# Interactive test

You can submit your own input to my program and it will be instantly processed at my server:

This live test is based on the Hackerrank problem.

This is equivalent to`echo "1 1 2" | ./104`

Output:

*Note:* the original problem's input `1 1 9`

__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)*

# Benchmark

The correct solution to the original Project Euler problem was found in 0.05 seconds on a Intel® Core™ i7-2600K CPU @ 3.40GHz.

(compiled for x86_64 / Linux, GCC flags: `-O3 -march=native -fno-exceptions -fno-rtti -std=c++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

May 12, 2017 submitted solution

May 12, 2017 added comments

# Hackerrank

see https://www.hackerrank.com/contests/projecteuler/challenges/euler104

My code solves **15** out of **15** test cases (score: **100%**)

# Difficulty

Project Euler ranks this problem at **25%** (out of 100%).

Hackerrank describes this problem as **easy**.

*Note:*

Hackerrank has strict execution time limits (typically 2 seconds for C++ code) and often a much wider input range than the original problem.

In my opinion, Hackerrank's modified problems are usually a lot harder to solve. As a rule thumb: brute-force is rarely an option.

# Links

projecteuler.net/thread=104 - **the** best forum on the subject (*note:* you have to submit the correct solution first)

Code in various languages:

Python: www.mathblog.dk/project-euler-104-fibonacci-pandigital/ (written by Kristian Edlund)

Java: github.com/nayuki/Project-Euler-solutions/blob/master/java/p104.java (written by Nayuki)

Scala: github.com/samskivert/euler-scala/blob/master/Euler104.scala (written by Michael Bayne)

# Heatmap

green problems solve the original Project Euler problem and have a perfect score of 100% at Hackerrank, too.

yellow problems score less than 100% at Hackerrank (but still solve the original problem).

gray problems are already solved but I haven't published my solution yet.

blue problems are solved and there wasn't a Hackerrank version of it at the time I solved it or I didn't care about it because it differed too much.

red problems are solved but exceed the time limit of one minute or the memory limit of 256 MByte.

*Please click on a problem's number to open my solution to that problem:*

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 |

I scored 12,983 points (out of 15100 possible points, top rank was 17 out of ≈60000 in August 2017) at Hackerrank's Project Euler+.

Look at my progress and performance pages to get more details.

My username at Project Euler is

**stephanbrumme**while it's stbrumme at Hackerrank.

# 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 103 - Special subset sums: optimum | Special subset sums: testing - problem 105 >> |