SKP's Java Problem Solving Series : Van Eck's Sequence (Naive & Fast Lookup)

[Question/Problem Statement is from GeeksforGeeks]

Algorithms/Data Structures - [Problem Solving] 

Given a Positive Integer N, The Task is to Print N Terms of the Van Eck’s Sequence. In Maths, Van Eck’s sequence is an Integer Sequence which is defined recursively as given below.    

-

-

 Let the First Term Be 0 i.e, a[0] = 0.
 Then for n>=0, If There Exists an m<n, such that a[m] = a[n]
 -
 Take the Largest such m and set a[n+1] = [n − m];
 Otherwise a[n+1] = 0, Start with a(1) = 0.
 

Example

[ First Few Terms of Van Eck’s Sequence are as Follows: ] 

0, 0, 1, 0, 2, 0, 2, 2, 1, 6, 0, 5, 0, 2, 6, 5, 4, 0, 5 …
 

Constraints
• [No Special Constraints Exist]

Input Format

[N is a Constant in the Java Code, For Example N=50]

 

 

Sample Output (Each Should Be on a Separate Line)

0, 0, 1, 0, 2, 0, 2, 2, 1, 6, 0, 5, 0, 2, 6, 5, 4, 0, 5, 3, 0, 3, 2, 9, 0, 4, 9, 3, 6, 14, 0, 6, 3, 5, 15, 0, 5, 3, 5, 2, 17, 0, 6, 11, 0, 3, 8, 0, 3, 3,

  

______________ 

 

 

 

/**
 * The Mathematical Puzzle of Van Eck's Sequence - Xebia Interview - 07-Dec-2021
 * [At the Experience Level of 17y - Was Interviewing for Java/Java EE Architect]
 */

// Given a Positive Integer N, The Task is to Print Nth Term of the Van Eck’s Sequence.
// In Maths, Van Eck’s sequence is an Integer Sequence which is defined Recursively As: 
//   
// Let the First Term Be 0 i.e, a[0] = 0.
// Then for n>=0, If There Exists an m<n 
// such that a[m] = a[n]
// -
// Take the Largest such m and set a[n+1] = [n − m];
// Otherwise a[n+1] = 0, Start with a(1) = 0.
// -  
// [ First Few Terms of Van Eck’s Sequence are as Follows: ] 
//  
// 0, 0, 1, 0, 2, 0, 2, 2, 1, 6, 0, 5, 0, 2, 6, 5, 4, 0, 5 … 
//  
// Input: N = 05, Output: 2
//  
// Input: N = 10, Output: 6 


/**
 * @author sumith.puri
 *
 */
public class VanEckSequence {

  static final int N=50;
  
  int[] printSeq    = null;
  int[] index1      = null;
  int val           = 0;
  int index         = 3;
 


  VanEckSequence() {

    init();
  }


  private void init() {

    printSeq    = new int[50];
    index1      = new int[200];
    val         = 0;
    index       = 3;
    index1[val] = 1;
  }


  public void linearVanEckSequence() {
    for (int i = 2; i < N; i++) {

      for (int j = i - 1; j > 0; j--) {
        if (printSeq[i - 1] == printSeq[j - 1]) {

          printSeq[index - 1] = i - j;          
          break;
        }
      }
      index++;
    }
  }


  public void fasterVanEckSequence() {
    
    int i = 0;
    
    for (int j = 2; j < N; j++) {

      i = j - 1;
      val = printSeq[i];

      // System.out.println("index:" + index + ":"+ val);
      if (index1[val] == 0) {

        printSeq[index-1] = 0;
        index1[val] = i + 1;
      } else {
        printSeq[index-1] = (i + 1) - index1[val];
        // optimal - fast lookup
        index1[val] = (i + 1);
      }
      index++;
    }
  }



  /**
   * @param args
   */
  public static void main(String[] args) {
    // TODO Auto-generated method stub


    VanEckSequence vancEckSequence = new VanEckSequence();
    vancEckSequence.linearVanEckSequence();

    System.out.println("Van Eck Sequence (Linear/Naive Algorithm)");
    System.out.println("----------------------------------------)");
    for (int i = 0; i < N; i++) {

      System.out.print(vancEckSequence.printSeq[i] + ", ");
    }

    System.out.println("\n");
    vancEckSequence.init();
    vancEckSequence.fasterVanEckSequence();

    System.out.println("Van Eck Sequence (Fast Lookup Algorithm)");
    System.out.println("----------------------------------------)");


    for (int i = 0; i < N; i++) {

      System.out.print(vancEckSequence.printSeq[i] + ", ");
    }

    System.out.println("");
    System.out.println("\n");
    System.out.println("Sumith Kumar Puri");
    System.out.println("SCJP 1.4, SCJP 5.0 / SCBCD 1.4, SCBCD 5.0");
    System.out.println("BB Spring 2.x, Hibernate 3.x, Java EE 6.x");
    System.out.println("Quest C, Quest C++, Quest Data Structures");
    System.out.println("Google India Code Jam 2005 Semi-Finalist.");
    System.out.println("Techgig Code Gladiators '15 Semi-Finalist");
    System.out.println("Societe Generale Brainwaves '15 Finalist.");
    System.out.println("Mphasis (Internal) Hackathon - Rank#7/106");
    System.out.println("Java Code Geeks, DZone MVB* & DZone Core*");
    System.out.println("Senior Member, ACM & Senior Member, IEEE.");
    System.out.println("Member*, CSI*; Foojay.IO & Developer.com*");
  }

}