Given a number N. The task is to find the first N terms of the Golomb Sequence. Golomb sequence is a non-decreasing integer sequence where the n-th term is equal to the number of times n appears in the sequence.
Input: N = 11
Output: 1 2 2 3 3 4 4 4 5 5 5
Explanation:
The first term is 1. 1 appears only once.
The second term is 2. 2 appears two times.
The third term is 2. 3 appears two times.
The fourth term is 3. 4 appears three times.
the fifth term is 3. 5 appears three times.Input: N = 6
Output: 1 2 2 3 3 4
Approach:
- Initialise the array arr[] with [1] as the Golomb sequence starts with 1.
- Store the value of last index in map M.
- For Golomb sequence till N:
- Initialise cnt = 0 and map the .
- If cnt is not equals to 0 then, then current element in Golomb sequence is the previous element in the sequence and decrease the cnt.
- Else the current element in Golomb sequence is equals to 1 + previous element in the sequence and cnt is updated as the value of map at current element in Golomb sequence and decrease the cnt.
- Map the current index with the current value at Golomb Sequence.
- Print all the element of Golomb Sequence stored in array arr[].
Below is the implementation of the above approach:
C++
// C++ program to find the first // N terms of Golomb Sequence #include "bits/stdc++.h" #define MAX 100001 using namespace std; // Function to print the Golomb // Sequence void printGolombSequence( int N) { // Initialise the array int arr[MAX]; // Initialise the cnt to 0 int cnt = 0; // First and second element // of Golomb Sequence is 0, 1 arr[0] = 0; arr[1] = 1; // Map to store the count of // current element in Golomb // Sequence map< int , int > M; // Store the count of 2 M[2] = 2; // Iterate over 2 to N for ( int i = 2; i <= N; i++) { // If cnt is equals to 0 // then we have new number // for Golomb Sequence // which is 1 + previous // element if (cnt == 0) { arr[i] = 1 + arr[i - 1]; cnt = M[arr[i]]; cnt--; } // Else the current element // is the previous element // in this Sequence else { arr[i] = arr[i - 1]; cnt--; } // Map the current index to // current value in arr[] M[i] = arr[i]; } // Print the Golomb Sequence for ( int i = 1; i <= N; i++) { cout << arr[i] << ' ' ; } } // Driver Code int main() { int N = 11; printGolombSequence(N); return 0; } |
Java
// Java program to find the first // N terms of Golomb Sequence import java.util.*; class GFG{ static int MAX = 1000 ; // Function to print the Golomb // Sequence static void printGolombSequence( int N) { // Initialise the array int []arr = new int [MAX]; for ( int i = 0 ; i < MAX; i++) arr[i] = 0 ; // Initialise the cnt to 0 int cnt = 0 ; // First and second element // of Golomb Sequence is 0, 1 arr[ 0 ] = 0 ; arr[ 1 ] = 1 ; // Map to store the count of // current element in Golomb // Sequence Map<Integer,Integer> M= new HashMap<Integer,Integer>(); // Store the count of 2 M.put( 2 , 2 ); // Iterate over 2 to N for ( int i = 2 ; i <= N; i++) { // If cnt is equals to 0 // then we have new number // for Golomb Sequence 1 2 2 3 3 4 4 4 5 5 5 // which is 1 + previous // element if (cnt == 0 ) { arr[i] = 1 + arr[i - 1 ]; cnt = M.get(arr[i]); cnt--; } // Else the current element // is the previous element // in this Sequence else { arr[i] = arr[i - 1 ]; cnt--; } // Map the current index to // current value in arr[] M.put(i, arr[i]); } // Print the Golomb Sequence for ( int i = 1 ; i <= N; i++) { System.out.print(arr[i]+ " " ); } } // Driver Code public static void main(String args[]) { int N = 11 ; printGolombSequence(N); } } // This code is contributed by Surendra_Gangwar |
Python3
# Python3 program to find the first # N terms of Golomb Sequence MAX = 100001 # Function to print the Golomb # Sequence def printGolombSequence(N): # Initialise the array arr = [ 0 ] * MAX # Initialise the cnt to 0 cnt = 0 # First and second element # of Golomb Sequence is 0, 1 arr[ 0 ] = 0 arr[ 1 ] = 1 # Map to store the count of # current element in Golomb # Sequence M = dict () # Store the count of 2 M[ 2 ] = 2 # Iterate over 2 to N for i in range ( 2 , N + 1 ): # If cnt is equals to 0 # then we have new number # for Golomb Sequence # which is 1 + previous # element if (cnt = = 0 ): arr[i] = 1 + arr[i - 1 ] cnt = M[arr[i]] cnt - = 1 # Else the current element # is the previous element # in this Sequence else : arr[i] = arr[i - 1 ] cnt - = 1 # Map the current index to # current value in arr[] M[i] = arr[i] # Print the Golomb Sequence for i in range ( 1 , N + 1 ): print (arr[i], end = " " ) # Driver Code N = 11 printGolombSequence(N) # This code is contributed by mohit kumar 29 |
C#
// C# program to find the first // N terms of Golomb Sequence using System; using System.Collections.Generic; class GFG{ static int MAX = 1000; // Function to print the Golomb // Sequence static void printGolombSequence( int N) { // Initialise the array int [] arr = new int [MAX]; for ( int i = 0; i < MAX; i++) arr[i] = 0; // Initialise the cnt to 0 int cnt = 0; // First and second element // of Golomb Sequence is 0, 1 arr[0] = 0; arr[1] = 1; // Map to store the count of // current element in Golomb // Sequence Dictionary< int , int > M = new Dictionary< int , int >(); // Store the count of 2 M.Add(2, 2); // Iterate over 2 to N for ( int i = 2; i <= N; i++) { // If cnt is equals to 0 // then we have new number // for Golomb Sequence 1 2 2 3 3 4 4 4 5 5 5 // which is 1 + previous // element if (cnt == 0) { arr[i] = 1 + arr[i - 1]; cnt = M[arr[i]]; cnt--; } // Else the current element // is the previous element // in this Sequence else { arr[i] = arr[i - 1]; cnt--; } // Map the current index to // current value in arr[] if (M.ContainsKey(i)) { M[i] = arr[i]; } else { M.Add(i, arr[i]); } } // Print the Golomb Sequence for ( int i = 1; i <= N; i++) { Console.Write(arr[i] + " " ); } } // Driver Code static void Main() { int N = 11; printGolombSequence(N); } } // This code is contributed by divyeshrabadiya07 |
Javascript
<script> // Javascript program to find the first // N terms of Golomb Sequence var MAX = 100001; // Function to print the Golomb // Sequence function printGolombSequence(N) { // Initialise the array var arr = Array(MAX); // Initialise the cnt to 0 var cnt = 0; // First and second element // of Golomb Sequence is 0, 1 arr[0] = 0; arr[1] = 1; // Map to store the count of // current element in Golomb // Sequence var M = new Map(); // Store the count of 2 M.set(2, 2); // Iterate over 2 to N for ( var i = 2; i <= N; i++) { // If cnt is equals to 0 // then we have new number // for Golomb Sequence // which is 1 + previous // element if (cnt == 0) { arr[i] = 1 + arr[i - 1]; cnt = M.get(arr[i]); cnt--; } // Else the current element // is the previous element // in this Sequence else { arr[i] = arr[i - 1]; cnt--; } // Map the current index to // current value in arr[] M.set(i, arr[i]); } // Print the Golomb Sequence for ( var i = 1; i <= N; i++) { document.write( arr[i] + ' ' ); } } // Driver Code var N = 11; printGolombSequence(N); </script> |
1 2 2 3 3 4 4 4 5 5 5
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!