FIBXOR01 - Editorial

PROBLEM LINK:

Practice | Contest
Author: Kapil Bansal
Tester: Kapil Bansal
Editorialist: Kapil Bansal

DIFFICULTY:

CAKEWALK, EASY

PREREQUISITES:

Maths, XOR Function

PROBLEM:

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:

QUICK EXPLANATION:

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.

SOLUTION:

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

Another Solution: Solution: 41998048 | CodeChef

for _ in range(int(input())):
    a, b, n = list(map(int, input().split()))
    ls = [a, b, a ^ b]
    print(ls[n % 3])
1 Like

I couldn’t understood why we do n%3?

1 Like
0      1      2      3     4     5    6    7     8     9   . . . 

Repeated Pattern:
0      1      2      0     1     2    0    1     2     0 . . .
0%3   1%3    2%3    3%3   4%3   5%3  6%3  . . .

moduling with 3 gives that repeated pattern
1 Like

Thanks…Now i understood what that question meant?