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

In this article, given three numbers **a**, **b** and **n,** where **a** and **b** are the first two terms of the XOR Fibonacci series, we have to find the **n ^{th}** 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,

## Leave a Reply