Skip to main content

solution: Special Fibonacci | codechef | Problem Code: FIBXOR01

 

Special Fibonacci Problem Code: FIBXOR01

Sankalp recently learned Fibonacci numbers and now he is studying different algorithms to find them. After getting bored of reading them, he came with his own new type of numbers. He defined them as follows:

You are given three integers a,b and n , calculate f(n).



Input

The input contains one or more independent test cases.

The first line of input contains a single integer T (1≤T≤103), the number of test cases.

Each of the T following lines contains three space-separated integers ab, and n (0≤a,b,n≤109) respectively.

Output

For each test case, output f(n).

Constraints

  • 1<=T<=1000
  • 0<=a,b,n<=109

Sample Input

4
86 77 15
93 35 86
92 49 21
62 27 90

Sample output

86
126
92
62

SOlution : 

This question looks like of recursion but if we think of it  and solve the equation further 

we will f(n) = f(n%3),that's why i first found n = n%3 , then make three values of n because now , n can only be 0 ,1 , 2. 

how to solve the equation the equation 

f(n) = f(n-1)^f(n-2);                                                                            .............eqn1

repacing n by n+1 , 

  we get , 

    f(n+1) = f(n)^f(n-1)                                                                    ..................eqn2

 adding eqn1 and eqn 2 

 we get , 

        f(n)^f(n+1)  = f(n-1)^f(n-2)^f(n)^f(n-1)  

 which is equal to

          f(n) ^ f(n+1) = f(n) ^ f(n-2)     

 =>  f(n+1) = f(n-2)     

  now replacing n+1 by n , 

 f(n) = f(n-3);                                          ................a

  also , f(n-3) = f(n-6)  right?                    .................b

  f(n-6) = f(n-9)                                            ................c          

and so on ,

then on adding a+b+c+........

f(n) = f(n-3*x)       where x is a random number such that 0< n - 3*x < 3 , that is it can simply the remainder after dividing it with 3.

f(n) = f(n%3);                        


#include <iostream>

using namespace std;

long long int f(int);

int main()

{

int t ; 

cin >> t;

while(t--)

{

    long int a , b , n ;

    cin >> a >> b >> n;

    long int d = a^b;

    n = n %3 ;

    if(n== 0)

    cout << a << "\n";

    if( n==1 )

    cout << b << "\n";

    if(n == 2)

    cout << d << "\n";

}

return 0;

}


Comments

Popular posts from this blog

leetcode 48 solution

  48 .  Rotate Image You are given an  n x n  2D  matrix  representing an image, rotate the image by  90  degrees (clockwise). You have to rotate the image  in-place , which means you have to modify the input 2D matrix directly.  DO NOT  allocate another 2D matrix and do the rotation.   Example 1: Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]] Example 2: Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]   Constraints: n == matrix.length == matrix[i].length 1 <= n <= 20 -1000 <= matrix[i][j] <= 1000 solution: class Solution { public:     void swap(int& a , int &b)     {         int c ;         c = a;         a = b;         b = c;     }     void transpose (vector<vector<int>...

2485. Find the Pivot Integer | Binary search

  Given a positive integer   n , find the   pivot integer   x   such that: The sum of all elements between  1  and  x  inclusively equals the sum of all elements between  x  and  n  inclusively. Return  the pivot integer  x . If no such integer exists, return  -1 . It is guaranteed that there will be at most one pivot index for the given input.   Example 1: Input: n = 8 Output: 6 Explanation: 6 is the pivot integer since: 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21. Example 2: Input: n = 1 Output: 1 Explanation: 1 is the pivot integer since: 1 = 1. Example 3: Input: n = 4 Output: -1 Explanation: It can be proved that no such integer exist.   Constraints: 1 <= n <= 1000 Solution : class Solution { publ ic:     int pivotInteger( int n ) {         int sum = (( n )*( n + 1 ))/ 2 ;         int i = 1 ;         int j =...

Regular Expression Matching Leetcode Solution

Regular Expression Matching Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where: '.' Matches any single character.​​​​ '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial). Example 1: Input: s = "aa", p = "a"  Output: false  Explanation: "a" does not match the entire string "aa". Example 2: Input: s = "aa", p = "a*"  Output: true  Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa". Example 3: Input: s = "ab", p = ".*"  Output: true  Explanation: ".*" means "zero or more (*) of any character (.)". Constraints: 1 <= s.length <= 20 1 <= p.length <= 20 s contains only lowercase English letters. p contains only lowercase Englis...