PROBLEM LINK:
DIFFICULTY:
CAKEWALK
PREREQUISITES:
Fibonacci Sequences.
PROBLEM:
Initially we are given an array A=[a_{1}, a_{2}, a_{3}....,a_{N}]. We are supposed to remove all elements occurring at odd indices in one step and we have to repeat this process until only single element remains. Let’s say we are left with some element a_{k}, so we need to output the last digit of the kth Fibonacci number.
STRATEGY
Fibonacci numbers follow the property : F'(N) = (F'(N-1) + F'(N-2)) \mod 10.
Here F'(N). represents the last digit of Nth fib number. Now if we look at the terms F'(N) is composed of, we can see that the pattern of F'(N) will start repeating at most after 10*10 terms, i.e we will get a cycle.
A simple trick to find when the cycle starts would be to find when again in the array the first and second terms consecutively appear. In our case here, cycle size = 60.
Now let’s get to the second part of the problem. Basically, we’re dividing our array A repeatedly by 2. So we can make an observation that the number which would be the highest power of 2 in the array would remain until the end.
FIBONACCI PATTERN
If we observe more closely, we can see that we’ll be only accessing these elements-
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048...
Since our cycle length is 60, we take the modulus of all these elements with 60 and we get-
1, 2, 4, 8, 16, 32, 4, 8, 16, 32, 4, 8...
We see that after the 1st and 2nd term, we have the repetition of 4th, 8th, 16th and 32nd term. So we only need to store these elements.
CODE
#include <iostream>
using namespace std;
typedef long long lld;
int log(lld N) {
int count = 0;
while (N) {
N /= 2;
count++;
}
return count-1;
}
int main() {
// freopen("input.txt", "r", stdin);
int T;
scanf("%d", &T);
int dp[] = {2, 3, 0, 9};
while (T--) {
lld N;
scanf("%lld", &N);
int max_power = log(N);
if (N==1) {
printf("0\n");
} else if (N==2 || N==3) {
printf("1\n");
} else {
printf("%d\n", dp[(max_power-2) % 4]);
}
}
return 0;
}
TIME COMPLEXITY
Time complexity of the algorithm discussed in this editorial is O(lg(N)) per test case.
