Maths, XOR Function
Sankalp recently learned Fibonacci numbers and now he is studying different algorithms to find them. After getting bored of reading them, he came with his own new type of numbers. He defined them as follows:
- f(0) = a;
- f(1) = b;
- f(n) = f(n-1) ^ f(n-2); when n>1, where ^ denotes the bitwise xor operation.
The problem can be solved easily if we know the properties of bitwise XOR function, or we can deduce them by seeing the pattern.
The properties we are going to use are:-
A XOR 0 = A
A XOR A = 0
Now, looking into the problem,
- f(0) = a,
- f(1) = b
- f(2) = a^b
- f(3) = (a^b^b) = a
and so on…
So, the pattern will be repeated after every third number.
def fibonacci(a, b, n): if(n == 0): return(a) elif(n == 1): return(b) elif(n == 2): return(a ^ b) return(fibonacci(a, b, n % 3)) T = int(input()) for i in range(T): a, b, n = [int(x) for x in input().split()] print(fibonacci(a, b, n))