Given three positive integers A, B, and N where A and B are the first two terms of the XOR Fibonacci series, the task is to find the sum of the first N terms of XOR Fibonacci series which is defined as follows:
F(N) = F(N – 1) ^ F(N – 2)
where ^ is the bitwise XOR and F(0) is 1 and F(1) is 2.
Examples:
Input: A = 0, B = 1, N = 3
Output: 2
Explanation: The first 3 terms of the XOR Fibonacci Series are 0, 1, 1. The sum of the series of the first 3 terms = 0 + 1 + 1 = 2.Input: a = 2, b = 5, N = 8
Output: 35
Naive Approach: The simplest approach is to generate the XOR Fibonacci series up to the first N terms and calculate the sum. Finally, print the sum of obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the sum of the// first N terms of XOR Fibonacci Seriesvoid findSum(int a, int b, int n){ // Base Case if (n == 1) { cout << a; return; } // Stores the sum of // the first N terms int s = a + b; // Iterate from [0, n-3] for (int i = 0; i < n - 2; i++) { // Store XOR of last 2 elements int x = a xor b; // Update sum s += x; // Update the first element a = b; // Update the second element b = x; } // Print the final sum cout << s;}// Driver Codeint main(){ int a = 2, b = 5, N = 8; // Function Call findSum(a, b, N); return 0;} |
Java
// Java program for the above approach import java.util.*;class GFG{ // Function to calculate the sum of the// first N terms of XOR Fibonacci Seriesstatic void findSum(int a, int b, int n){ // Base Case if (n == 1) { System.out.println(a); return; } // Stores the sum of // the first N terms int s = a + b; // Iterate from [0, n-3] for(int i = 0; i < n - 2; i++) { // Store XOR of last 2 elements int x = a ^ b; // Update sum s += x; // Update the first element a = b; // Update the second element b = x; } // Print the final sum System.out.println(s);}// Driver Codepublic static void main(String[] args){ int a = 2, b = 5, N = 8; // Function Call findSum(a, b, N);}}// This code is contributed by jana_sayantan |
Python3
# Python3 program for the above approach# Function to calculate the sum of the# first N terms of XOR Fibonacci Seriesdef findSum(a, b, N): # Base case if N == 1: print(a) return # Stores the sum of # the first N terms s = a + b # Iterate from [0, n-3] for i in range(0, N - 2): # Store XOR of last 2 elements x = a ^ b # Update sum s += x # Update the first element a = b # Update the second element b = x # Print the final sum print(s) return# Driver codeif __name__ == '__main__': a = 2 b = 5 N = 8 # Function call findSum(a, b, N)# This code is contributed by MuskanKalra1 |
C#
// C# program for the above approach using System;class GFG{ // Function to calculate the sum of the// first N terms of XOR Fibonacci Seriesstatic void findSum(int a, int b, int n){ // Base Case if (n == 1) { Console.WriteLine(a); return; } // Stores the sum of // the first N terms int s = a + b; // Iterate from [0, n-3] for(int i = 0; i < n - 2; i++) { // Store XOR of last 2 elements int x = a ^ b; // Update sum s += x; // Update the first element a = b; // Update the second element b = x; } // Print the final sum Console.WriteLine(s);} // Driver Codepublic static void Main(){ int a = 2, b = 5, N = 8; // Function Call findSum(a, b, N);}}// This code is contributed by susmitakundugoaldanga |
Javascript
<script>// Javascript program for the above approach // Function to calculate the sum of the // first N terms of XOR Fibonacci Series function findSum( a ,b, n) { // Base Case if (n == 1) { document.write(a); return; } // Stores the sum of // the first N terms let s = a + b; // Iterate from [0, n-3] for ( i = 0; i < n - 2; i++) { // Store XOR of last 2 elements let x = a ^ b; // Update sum s += x; // Update the first element a = b; // Update the second element b = x; } // Print the const sum document.write(s); } // Driver Code let a = 2, b = 5, N = 8; // Function Call findSum(a, b, N);// This code is contributed by 29AjayKumar </script> |
Output:
35
Time Complexity: O(N)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is based on the following observation:
Since a ^ a = 0 and it is given that
F(0) = a and F(1) = b
Now, F(2) = F(0) ^ F(1) = a ^ b
And, 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
…
It can be observed that the series repeats itself after every 3 numbers. So, the following three cases arises:
- If N is divisible by 3: Sum of the series is (N / 3) * (a + b + x), where x is XOR of a and b.
- If N % 3 leaves a remainder 1: Sum of the series is (N / 3)*(a + b + x) + a, where x is the Bitwise XOR of a and b.
- If N % 3 leaves a remainder 2: Sum of the series is (N / 3)*(a + b + x) + a + b, where x is the Bitwise XOR of a and b.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate sum of the// first N terms of XOR Fibonacci Seriesvoid findSum(int a, int b, int n){ // Store the sum of first n terms int sum = 0; // Store XOR of a and b int x = a ^ b; // Case 1: If n is divisible by 3 if (n % 3 == 0) { sum = (n / 3) * (a + b + x); } // Case 2: If n % 3 leaves remainder 1 else if (n % 3 == 1) { sum = (n / 3) * (a + b + x) + a; } // Case 3: If n % 3 leaves remainder 2 // on division by 3 else { sum = (n / 3) * (a + b + x) + a + b; } // Print the final sum cout << sum;}// Driver Codeint main(){ int a = 2, b = 5, N = 8; // Function Call findSum(a, b, N); return 0;} |
Java
// Java program for the above approachimport java.util.*; class GFG{// Function to calculate sum of the// first N terms of XOR Fibonacci Seriesstatic void findSum(int a, int b, int n){ // Store the sum of first n terms int sum = 0; // Store XOR of a and b int x = a ^ b; // Case 1: If n is divisible by 3 if (n % 3 == 0) { sum = (n / 3) * (a + b + x); } // Case 2: If n % 3 leaves remainder 1 else if (n % 3 == 1) { sum = (n / 3) * (a + b + x) + a; } // Case 3: If n % 3 leaves remainder 2 // on division by 3 else { sum = (n / 3) * (a + b + x) + a + b; } // Print the final sum System.out.print(sum);}// Driver Codepublic static void main(String[] args){ int a = 2, b = 5, N = 8; // Function Call findSum(a, b, N);}}// This code is contributed by shivanisinghss2110 |
Python3
# Python3 program for the above approach# Function to calculate sum of the# first N terms of XOR Fibonacci Seriesdef findSum(a, b, N): # Store the sum of first n terms sum = 0 # Store xor of a and b x = a ^ b # Case 1: If n is divisible by 3 if N % 3 == 0: sum = (N // 3) * (a + b + x) # Case 2: If n % 3 leaves remainder 1 elif N % 3 == 1: sum = (N // 3) * (a + b + x) + a # Case 3: If n % 3 leaves remainder 2 # on division by 3 else: sum = (N // 3) * (a + b + x) + a + b # Print the final sum print(sum) return# Driver codeif __name__ == '__main__': a = 2 b = 5 N = 8 # Function call findSum(a, b, N)# This code is contributed by MuskanKalra1 |
C#
// C# program for the above approachusing System;class GFG{// Function to calculate sum of the// first N terms of XOR Fibonacci Seriesstatic void findSum(int a, int b, int n){ // Store the sum of first n terms int sum = 0; // Store XOR of a and b int x = a ^ b; // Case 1: If n is divisible by 3 if (n % 3 == 0) { sum = (n / 3) * (a + b + x); } // Case 2: If n % 3 leaves remainder 1 else if (n % 3 == 1) { sum = (n / 3) * (a + b + x) + a; } // Case 3: If n % 3 leaves remainder 2 // on division by 3 else { sum = (n / 3) * (a + b + x) + a + b; } // Print the final sum Console.Write(sum);}// Driver Codepublic static void Main(String[] args){ int a = 2, b = 5, N = 8; // Function Call findSum(a, b, N);}}// This code is contributed by shivanisinghss2110 |
Javascript
<script>// JavaScript program for the above approach // Function to calculate sum of the // first N terms of XOR Fibonacci Series function findSum(a , b , n) { // Store the sum of first n terms var sum = 0; // Store XOR of a and b var x = a ^ b; // Case 1: If n is divisible by 3 if (n % 3 == 0) { sum = parseInt(n / 3) * (a + b + x); } // Case 2: If n % 3 leaves remainder 1 else if (n % 3 == 1) { sum =parseInt(n / 3)* (a + b + x) + a; } // Case 3: If n % 3 leaves remainder 2 // on division by 3 else { sum = parseInt(n / 3)* (a + b + x) + a + b; } // Print the final sum document.write(sum); } // Driver Code var a = 2, b = 5, N = 8; // Function Call findSum(a, b, N);// This code is contributed by aashish1995</script> |
Output
35
Method 3: The function xor_fibonacci_sum computes the sum of the first n terms of a modified Fibonacci sequence where each term is obtained by XORing the previous two terms. The sequence starts with a and b as the first two terms.
In the code, the Fibonacci sequence is stored in the list f. The list is built up by iterating through n+1 terms and appending the XOR of the previous two terms to the list. The sum of the first n terms of the sequence is returned by summing the first n+1 elements of the list f.
C++
#include <iostream>int xor_fibonacci_sum(int n, int a, int b) { int f[n+1]; f[0] = a; f[1] = b; for (int i = 2; i <= n; i++) { f[i] = f[i-1] ^ f[i-2]; } int sum = 0; for (int i = 0; i <= n; i++) { sum += f[i]; } return sum;}int main() { int n = 3, a = 0, b = 1; int sum = xor_fibonacci_sum(n, a, b); std::cout << "Sum: " << sum << std::endl; return 0;} |
Python3
def xor_fibonacci_sum(n,a,b): f = [a, b] for i in range(2, n+1): f.append(f[i-1] ^ f[i-2]) return sum(f[:n+1])n = 3; a=0; b=1sum = xor_fibonacci_sum(n,a,b)print(sum) |
Javascript
// JavaScript implementation of the above approach. function xor_fibonacci_sum(n, a, b) { let f = new Array(n+1); f[0] = a; f[1] = b; for (let i = 2; i <= n; i++) { f[i] = f[i-1] ^ f[i-2]; } let sum = 0; for (let i = 0; i <= n; i++) { sum += f[i]; } return sum;}let n = 3, a = 0, b = 1;let sum = xor_fibonacci_sum(n, a, b);console.log("Sum:", sum);// The code is contributed by Nidhi goel. |
Java
public class Main { public static int xorFibonacciSum(int n, int a, int b) { int[] f = new int[n+1]; f[0] = a; f[1] = b; for (int i = 2; i <= n; i++) { f[i] = f[i-1] ^ f[i-2]; } int sum = 0; for (int i = 0; i <= n; i++) { sum += f[i]; } return sum; } public static void main(String[] args) { int n = 3; int a = 0; int b = 1; int sum = xorFibonacciSum(n, a, b); System.out.println(sum); }} |
C#
using System;class Program { static int xor_fibonacci_sum(int n, int a, int b) { int[] f = new int[n+1]; f[0] = a; f[1] = b; for (int i = 2; i <= n; i++) { f[i] = f[i-1] ^ f[i-2]; } int sum = 0; for (int i = 0; i <= n; i++) { sum += f[i]; } return sum; } static void Main(string[] args) { int n = 3, a = 0, b = 1; int sum = xor_fibonacci_sum(n, a, b); Console.WriteLine("Sum: " + sum); }} |
Output
2
In the example provided, n is set to 3, a is set to 0, and b is set to 1. The function xor_fibonacci_sum is called and the result is printed. The output will be 2, which is the sum of the first 3 terms of the XOR-based Fibonacci sequence starting with 0 and 1.
Time Complexity: O(N)
Auxiliary Space: O(1)
Method 4: Using Bit manipulation (Efficient Approach)
We can also calculate the sum of the first N terms of the XOR Fibonacci series using bit manipulation. In this approach, we iterate through the bits of N and calculate the sum of the XOR Fibonacci series using bit manipulation.
Step-by-Step Algorithm :
- Define a function findSum that takes in three integer parameters a, b, and n. a and b are the first two terms of the XOR Fibonacci series, and n is the number of terms we want to sum.
- Initialize a variable sum to 0. This variable will store the sum of the first N terms of the XOR Fibonacci series.
- Initialize a variable k to 0. This variable will keep track of the position of the current bit we will iterating through.
- Start a while loop that continues while n is greter than 0 and then iterate through the bits of n one at a time.
- Inside the while loop, check if the least significant bit of n is set or not using the bitwise AND operator with 1. If the bit is set, we need to calculate the sum of the XOR Fibonacci series up to that bit.
- To calculate the sum up to the current bit, we first left shift a by k bits and XOR it with sum. This will add the sum of the XOR Fibonacci series up to the previous bit to the current sum.
- Next, we calculate the next term of the XOR Fibonacci series using the same method as in the previous approach.
- Right shift n by 1 bit to move to the next bit and increment k by 1 to keep track of the position of the current bit.
- After the while loop finishes, the variable sum will contain the sum of the first N terms of the XOR Fibonacci series. Print the value of sum.
C++
#include <iostream>using namespace std;void findSum(int a, int b, int n){int sum = 0;int k = 0;while (n > 0) { if (n & 1) { sum ^= (a << k); int x = a xor b; b = (b << k) xor a; a = x; } n >>= 1; k++;}cout << sum;}int main(){int a = 0, b = 1, N = 3;findSum(a, b, N);return 0;} |
Java
// Java code additionimport java.io.*;public class Main { // This function calculates the sum of the first N terms // of the Fibonacci sequence static void findSum(int a, int b, int n) { int sum = 0; int k = 0; while (n > 0) { if ((n & 1) == 1) { sum ^= (a << k); int x = a ^ b; b = (b << k) ^ a; a = x; } n >>= 1; k++; } System.out.println(sum); } public static void main(String[] args) { // The starting values of the sequence int a = 0, b = 1; // The number of terms to sum int N = 3; // Call the function to calculate the sum findSum(a, b, N); }}// The code is contributed by Arushi Goel. |
Python3
# Pyhton program for the above approachdef findSum(a: int, b: int, n: int) -> None: sum = 0 k = 0 while n > 0: if n & 1: sum ^= (a << k) x = a ^ b b = (b << k) ^ a a = x n >>= 1 k += 1 print(sum)if __name__ == '__main__': a = 0 b = 1 N = 3 findSum(a, b, N)# This code is contributed by rishab |
C#
using System;class Program { // This function calculates the sum of the first N terms // of the Fibonacci sequence static void findSum(int a, int b, int n) { int sum = 0; int k = 0; while (n > 0) { if ((n & 1) == 1) { sum ^= (a << k); int x = a ^ b; b = (b << k) ^ a; a = x; } n >>= 1; k++; } Console.WriteLine(sum); } static void Main(string[] args) { // The starting values of the sequence int a = 0, b = 1; // The number of terms to sum int N = 3; // Call the function to calculate the sum findSum(a, b, N); }}// This code is contributed by sarojmcy2e |
Javascript
// Javascript code addition function findSum(a, b, n){ let sum = 0; let k = 0; while (n > 0) { if (n & 1) { sum ^= (a << k); let x = a^ b; b = (b << k) ^ a; a = x; } n >>= 1; k++; } console.log(sum);}let a = 0, b = 1, N = 3;findSum(a, b, N);// The code is contributed by Nidhi goel. |
Output
2
Complexity Analysis :
Time Complexity: O(log n) where n is the number of terms
This is because we iterate through the bits of n one at a time, and there are log n bits in the binary representation of n.
Space Complexity: O(1)
This is because we only use a constant amount of extra space to store the variables sum, k, a, b, n, and x
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
