FIBXOR01 - Editorial

editorial
,
1

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

Another Solution: CodeChef: Practical coding for everyone

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

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

1 Like
4 
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
2 Likes
5

Thanks…Now i understood what that question meant?