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 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,
Leave a Reply