Golomb sequence

Difficulty Level Easy
Frequently asked in Cadence India Indeed Times Internet Yatra
Dynamic Programming SequenceViews 1865

Problem Statement

The problem “Golomb sequence” states that you are given an input integer n and you need to find all the elements of Golomb sequence until nth element.

Example

n = 8
1 2 2 3 3 4 4 4

Explanation
The first 8 terms of the Golomb sequence are found and printed. Since the output denotes the first 8 elements of the Golomb Sequence, the output is correct.

Approach

In mathematics, the given sequence is also called Silverman’s Sequence. The sequence is named after Solomon W. Golomb. It is a non-decreasing integer sequence where a(n) is the number of times that n occurs in the sequence. The Golomb sequence’s first element is 1. For example, a1 = 1 says that 1 only occurs once in the sequence, so a2 cannot be 1 too, but it can be, and therefore must be 2.

The first few terms of the sequence are 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12.

We know the recurrence relation for generating the elements of the Golomb sequence. The recursive formula is

Golomb sequence
Using the recursive formula we will solve the problem. One way is to solve the problem using recursion. But that will cost us exponential time complexity because we will be calculating the same values again and again. Because as we can see from the recurrence relation the nth element of the sequence is dependent on previously computed terms. So we will use Dynamic Programming to solve the problem since using it, we will not have to re-compute other values.

Code

C++ code for Golomb Sequence

#include <bits/stdc++.h>
using namespace std;

int main(){
  // number of elements of Golomb sequence which are required
  int n;cin>>n;

  cout<<1<<" ";
  int dp[n+1];
  dp[1] = 1;
  for(int i=2;i<=n;i++){
    dp[i] = 1 + dp[i-dp[dp[i-1]]];
    cout<<dp[i]<<" ";
  }
}
10
1 2 2 3 3 4 4 4 5 5

Java code for Golomb Sequence

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    // number of elements of Golomb sequence which are required
    int n = sc.nextInt();

    System.out.print("1 ");
    int dp[] = new int[n+1];
    dp[1] = 1;
    for(int i=2;i<=n;i++){
      dp[i] = 1 + dp[i-dp[dp[i-1]]];
      System.out.print(dp[i]+" ");
    }
  }
}
10
1 2 2 3 3 4 4 4 5 5

Complexity Analysis

Time Complexity

O(N), because the nth element depends on a single previously calculated element which makes this operation O(1) time complex for each element. Since there are n elements, the time complexity is linear.

Space Complexity

O(N), since we are storing n elements, the space complexity is also linear.

Translate ยป