## DEV Community is a community of 607,586 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# School problem from senior developer interview

I was asked this problem years ago at interview for Java developer. It was about using BigInt really, but that's not important. I later slightly extended it and started asking when I interview other people in my turn (usually big-data or data science developers). Curiously, it puzzles about 40% people pretending for several kilo-dollars salary :o

Code could be written in 3 minutes (e.g. in `Python`), but then people sometimes stuck for hour. I think most of you, Friends, will solve it easily - but you can check your colleagues for fun. So here it is:

### Statement

Fibonacci numbers (we all know them) are defined as:

``````fib = [0, 1, 1, 2, 3, 5, 8, ...]

# or in other words
fib[0] = 0
fib[1] = 1
# ...
fib[n] = fib[n-1] + fib[n-2]
``````

Write the program (usually in Python) which finds index, where Fibonacci value ends with specific digits. For example ending `12345` could be found at fib[155].

Then find the following:

``````For which index X fib[X] ends with five digits `55555` ?
For which index Y fib[Y] ends with seven digits `7770777` ?
For which index Z fib[Z] ends with eight digits `20200123` ?
``````

This value `20200123` is just today's date, nothing special about it. :)

P.S. I think it's ok to drop X, Y, Z in the comments when you find them. Code - as you wish...

P.P.S. if can't solve at once, this problem may give inspiration, though of course you'd better try solving on your own first... If it is necessary I'll update the post with explanation in about three days, though I believe it is too simple for most of readers.

## Discussion (8)

Jannik Wempe

That was a fun task and I could refresh some aspects of python doing it. Thanks!

Until now (programm is still executing) I just have the following solution:
X -> 92740
Y -> ???
Z -> ???

I am pretty sure that my solution is far from perfect, since it has a huge runtime and memory consumption. Therefore I'm really looking forward to a better approach.

Rodion Gorkovenko

Jannik, Hi!

Thanks for attempt!

Yep, it is just a matter of making it work without speed degradation due to number length increase :)

Arseniy Krasnov • Edited

There a trick you can use:

last 2 and 3 digits of fibonacci repeats each 1500 terms
last 4 digits repeats each 15,000
last 5 digits repeats each 150,000
last 6 digits repeats each 1,500,000
last 7 digits repeats each 15,000,000

x = 92.740
y = 4.562.603
z = 280.555.264

Rodion Gorkovenko

Nice idea about finding "the loop length" after which "endings" repeat :) Perhaps some other puzzle could be invented from it.

However my approach was simpler - just taking modulo by `10eX` where `X` is amount of digits in the number we seek. Then numbers won't grow longer than this.

I suspect your and mine approaches are really two versions of the same fact, however

Michael

Hi,

so far I have
x - 92.740
y - 4.562.603

Have a nice weekend
Michael

Rodion Gorkovenko

Michael, Hi!

Thanks for try! Judging by "so far" it seems you also use straightforward implementation which becomes a bit slower as the values grew :)

Good luck!

Michael

Hi Rodion,

yes, I started with a default-Fibonacci, and that take a lot of time ;O)

With a little optimization (using only the necessary decimal places), the last value can be found within minutes.

b: 54212345 idx 155
b: 77255555 idx 92740
b: 67770777 idx 4562603
b: 20200123 idx 145555264

So I found z - 145.555.264

Is that correct?