How to find the Nth XOR Fibonacci number in C++

In this article, given three numbers ab and n, where a and b are the first two terms of the XOR Fibonacci series, we have to find the nth term. The Nth term of the XOR Fibonacci series is defined as F(N) = F(N – 1) ^ F(N – 2) where ^ is the operator for bitwise XOR. The time complexity of our code is O(1).

Nth XOR Fibonacci number in C++

Let’s take the help of an example.

Input: a = 1, b = 2, N = 5
Output: 3

Working:

F(0) = 1
F(1) = 2
F(2) = 1 ^ 2 = 3
F(3) = 2 ^ 3 = 1
F(4) = 1 ^ 3 = 2
F(5) = 1 ^ 2 = 3

Code Implementation:

```#include <bits/stdc++.h>
using namespace std;

int nXorFib(int n, int a, int b)
{
if (n == 0)
return a;
if (n == 1)
return b;
if (n == 2)
return (a ^ b);
return nXorFib(n % 3, a, b);
}

int main()
{
int a,b,n;
cout<<"Enter the value of a \n";
cin>>a;
cout<<"Enter the value of b \n";
cin>>b;
cout<<"Enter the value of n \n";
cin>>n;
cout<<nXorFib(n, a, b);
return 0;
}
```

Working of Code:

Since, a ^ a = 0 and it is given that

F(0) = a , F(1) = b

F(2) = F(0) ^ F(1) = a ^ b
F(3) = F(1) ^ F(2) = b ^ (a ^ b) = a
F(4) = a ^ b ^ a = b
F(5) = a ^ b
F(6) = a
F(7) = b
F(8) = a ^ b and so on.

We can notice that the result repeats itself every 3 numbers. Thus the answer is F(N % 3) where F(0) = a, F(1) = b and F(2) = a ^ b.

I hope, you have understood how our program works to find the Nth XOR Fibonacci number in C++ language.

You may also learn,