Coders Packet

How to get specific element from the XORinacci Series in minimum time complexity in Java

By Dhanada Kapre

In the XORinacci series, the preceding two elements are XORed to get the next element in the series in Java.

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation:
f(n) = f(n-1) + f(n-2)
with seed values
f(0) = 0 and f(1) = 1.

Similarly, in the XORinacci series, we will be having values of F0 and F1 which is not fixed for all examples unlike in Fibonacci where F0 and F1 are always fixed as 0 and 1 respectively.

In XORinacci series,
let f(0) = a, f(1) = b
f(n)=f(n−1)⊕f(n−2) when n>1, where ⊕ denotes the bitwise XOR operation.

Now, instead of using recursion or iteration, we will focus on finding the pattern that the series is following.
so, for example,
let f(0) = 3
f(1) = 4
and let's say we are asked to find f(7).
i) f(2)=f(0)⊕f(1)=3⊕4=7
ii) f(3)=f(1)⊕f(2)=4⊕7=3
iii) f(4)=f(2)⊕f(3)=7⊕3=4
iv) f(5)=f(3)⊕f(4)=3⊕4=7
v) f(6)=f(4)⊕f(5)=3⊕4=3
vi) f(7)=f(5)⊕f(6)=3⊕4=4

So, from above we have got a pattern that every element is the same as its third preceded element in the series and we just need to calculate the first three elements.
i.e. f(0) = f(3) = f(6) =... ,
f(1) = f(4) = f(7) = ... and
f(2) = f(5) = f(8) and so on.

And, this pattern of repetition is the same for all values of f(0) and f(1).

import java.util.*;

public class XORinacci {

  public static void main(String[] args) {
    
    Scanner sc = new Scanner(System.in);
      
    System.out.print("f(0) = ");
      int a = sc.nextInt();
      System.out.println();
      System.out.print("f(1) = ");
      int b = sc.nextInt();
      System.out.println();
      System.out.print("Enter the index value to fetch the specific element: ");
      int n = sc.nextInt();
      System.out.println();
      int[] arr = new int[3];
      arr[0]  = a;
      if(n>0)
        arr[1] = b;
      if(n>=2)
      {
        arr[2] = arr[1] ^ arr[0];
      }
      System.out.print("f(n)=");
      System.out.println(arr[n%3]);
    
  }
 
}

Output for XORinacci code

Download Complete Code

Comments

No comments yet