Dados tres enteros positivos A , B y N donde A y B son los primeros dos términos de la serie XOR de Fibonacci , la tarea es encontrar la suma de los primeros N términos de la serie XOR de Fibonacci que se define de la siguiente manera:
F(N) = F(N – 1) ^ F(N – 2)
donde ^ es el XOR bit a bit y F(0) es 1 y F(1) es 2 .
Ejemplos:
Entrada: A = 0, B = 1, N = 3
Salida: 2
Explicación: Los primeros 3 términos de la Serie XOR de Fibonacci son 0, 1, 1. La suma de la serie de los primeros 3 términos = 0 + 1 + 1 = 2Entrada: a = 2, b = 5, N = 8
Salida: 35
Enfoque ingenuo: el enfoque más simple es generar la serie XOR Fibonacci hasta los primeros N términos y calcular la suma. Finalmente, imprima la suma de los obtenidos.
A continuación se muestra la implementación del enfoque anterior:
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 Series
void 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 Code
int 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 Series
static 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 Code
public 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 Series def 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 code if __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 Series
static 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 Code
public 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>
Producción:
35
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente: Para optimizar el enfoque anterior, la idea se basa en la siguiente observación:
Como a ^ a = 0 y se da que
F(0) = a y F(1) = b
Ahora, F(2) = F(0) ^ F(1) = a ^ b
Y, 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
…
Se puede observar que la serie se repite cada 3 números. Entonces, se presentan los siguientes tres casos:
- Si N es divisible por 3: La suma de la serie es (N/3) * (a + b + x) , donde x es XOR de a y b .
- Si N % 3 deja un resto 1: La suma de la serie es (N / 3)*(a + b + x) + a , donde x es el XOR bit a bit de a y b .
- Si N % 3 deja un resto 2: La suma de la serie es (N / 3)*(a + b + x) + a + b , donde x es el XOR bit a bit de a y b .
A continuación se muestra la implementación del enfoque anterior:
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 Series
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
cout << sum;
}
// Driver Code
int 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 sum of the
// first N terms of XOR Fibonacci Series
static 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 Code
public 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 Series def 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 code if __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 sum of the
// first N terms of XOR Fibonacci Series
static 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 Code
public 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>
Producción
35
Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por prathamjha5683 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA