Even indexed arrays

#1

i have a doubt in the first question of september long challenge on codechef
i just want to know the logic of finding the element which came after repeatedly after extracting even indexed elements of the fibonacci sequence
for example-{0,1,1,2,3,5,8}->{1,2,5}->{2}
so the last number is 2
can u tell me the shortest possible algorith for this, i tried to sort out using for loops but the time limit exceeded, here the number of elemnts in the sequence is 10 power 18(10^18)

#2

hey @sktg99, let’s take one big example:
suppose n = 17:
numbers : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987
indexes : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 , 17
after 1st iteration remaining indexes will be: 2, 4, 6, 8, 10, 12, 14, 16
after 2nd: 4, 8, 12, 16
after 3rd: 8, 16
after 4th: 16

if you can see the pattern here, you have to find fib(n) where:
n = 2^( (int) log17/log2 )

I think this will help, now you just have to implement fast fibonacci here…

#3

how that log9/log2 come

#4

@sktg99, sry… log17 for my example, log7 for urs

#5

it’s working thank you

#6

can u pls check this code
its showing wrong answer
we have to only show the last digit of fibonacci seq.