Given an integer ‘n’, print the first ‘n’ terms of the Moser-de Bruijn Sequence. Moser-de Bruijn sequence is the sequence obtained by adding up the distinct powers of the number 4 (For example, 1, 4, 16, 64, etc).
Examples:
Input : 5 Output : 0 1 4 5 16 Input : 10 Output : 0 1 4 5 16 17 20 21 64 65
It is observed that the terms of the sequence follow the recurrence relation :
1) S(2 * n) = 4 * S(n) 2) S(2 * n + 1) = 4 * S(n) + 1 with S(0) = 0 and S(1) = 1
It may be noted here that any number which is the sum of non-distinct powers of 4 is not a part of the sequence. For example, 8 is not a part of the sequence because it is formed as the sum of non-distinct powers of 4, which are 4 and 4.
Thus, any number which is not a power of 4 and is present in the sequence must be the sum of the distinct powers of 4.
For example, 21 is a part of the sequence, even though it is not a power of 4, because it is the sum of the distinct powers of 4, which are 1, 4, and 16.
Employ the recurrence relation discussed above to generate the sequence efficiently.
C++
// CPP code to generate first 'n' terms // of the Moser-de Bruijn Sequence#include <bits/stdc++.h>using namespace std;// Function to generate nth term // of Moser-de Bruijn Sequenceint gen(int n){ // S(0) = 0 if (n == 0) return 0; // S(1) = 1 else if (n == 1) return 1; // S(2 * n) = 4 * S(n) else if (n % 2 == 0) return 4 * gen(n / 2); // S(2 * n + 1) = 4 * S(n) + 1 else if (n % 2 == 1) return 4 * gen(n / 2) + 1;}// Generating the first 'n' terms // of Moser-de Bruijn Sequencevoid moserDeBruijn(int n){ for (int i = 0; i < n; i++) cout << gen(i) << " "; cout << "\n";}// Driver Codeint main(){ int n = 15; cout << "First " << n << " terms of " << "Moser-de Bruijn Sequence : \n"; moserDeBruijn(n); return 0;} |
Java
// Java code to generate first 'n' terms // of the Moser-de Bruijn Sequenceclass GFG { // Function to generate nth term // of Moser-de Bruijn Sequencepublic static int gen(int n){ // S(0) = 0 if (n == 0) return 0; // S(1) = 1 else if (n == 1) return 1; // S(2 * n) = 4 * S(n) else if (n % 2 == 0) return 4 * gen(n / 2); // S(2 * n + 1) = 4 * S(n) + 1 else if (n % 2 == 1) return 4 * gen(n / 2) + 1; return 0;}// Generating the first 'n' terms // of Moser-de Bruijn Sequencepublic static void moserDeBruijn(int n){ for (int i = 0; i < n; i++) System.out.print(gen(i) + " "); System.out.println();}// Driver Codepublic static void main(String args[]){ int n = 15; System.out.println("First " + n + " terms of " + "Moser-de Bruijn Sequence : "); moserDeBruijn(n);}}// This code is contributed by JaideepPyne. |
Python3
# Python code to generate first # 'n' terms of the Moser-de # Bruijn Sequence# Function to generate nth term# of Moser-de Bruijn Sequencedef gen(n): # S(0) = 0 if n == 0: return 0 # S(1) = 1 elif n ==1: return 1 # S(2 * n) = 4 * S(n) elif n % 2 ==0: return 4 * gen(n // 2) # S(2 * n + 1) = 4 * S(n) + 1 elif n % 2 == 1: return 4 * gen(n // 2) +1# Generating the first 'n' terms# of Moser-de Bruijn Sequencedef moserDeBruijn(n): for i in range(n): print(gen(i), end = " ")# Driver Programn = 15print("First", n, "terms of ", "Moser-de Bruijn Sequence:")moserDeBruijn(n)# This code is contributed by Shrikant13 |
C#
// C# code to generate first 'n' terms // of the Moser-de Bruijn Sequenceusing System;class GFG { // Function to generate nth term // of Moser-de Bruijn Sequencepublic static int gen(int n){ // S(0) = 0 if (n == 0) return 0; // S(1) = 1 else if (n == 1) return 1; // S(2 * n) = 4 * S(n) else if (n % 2 == 0) return 4 * gen(n / 2); // S(2 * n + 1) = 4 * S(n) + 1 else if (n % 2 == 1) return 4 * gen(n / 2) + 1; return 0;}// Generating the first 'n' terms // of Moser-de Bruijn Sequencepublic static void moserDeBruijn(int n){ for (int i = 0; i < n; i++) Console.Write(gen(i) + " "); Console.WriteLine();}// Driver Codepublic static void Main(){ int n = 15; Console.WriteLine("First " + n + " terms of " + "Moser-de Bruijn Sequence : "); moserDeBruijn(n);}}// This code is contributed by anuj_67. |
PHP
<?php// PHP code to generate first 'n' terms // of the Moser-de Bruijn Sequence// Function to generate nth term // of Moser-de Bruijn Sequencefunction gen($n){ // S(0) = 0 if ($n == 0) return 0; // S(1) = 1 else if ($n == 1) return 1; // S(2 * n) = 4 * S(n) else if ($n % 2 == 0) return 4 * gen($n / 2); // S(2 * n + 1) = 4 * S(n) + 1 else if ($n % 2 == 1) return 4 * gen($n / 2) + 1;}// Generating the first 'n' terms // of Moser-de Bruijn Sequencefunction moserDeBruijn($n){ for ($i = 0; $i < $n; $i++) echo(gen($i) . " "); echo("\n");}// Driver Code$n = 15;echo("First " . $n . " terms of " . "Moser-de Bruijn Sequence : \n");echo(moserDeBruijn($n));// This code is contributed by Ajit.?> |
Javascript
<script>// Javascript code to generate first 'n' terms // of the Moser-de Bruijn Sequence// Function to generate nth term // of Moser-de Bruijn Sequencefunction gen(n){ // S(0) = 0 if (n == 0) return 0; // S(1) = 1 else if (n == 1) return 1; // S(2 * n) = 4 * S(n) else if (n % 2 == 0) return 4 * gen(parseInt(n / 2, 10)); // S(2 * n + 1) = 4 * S(n) + 1 else if (n % 2 == 1) return 4 * gen(parseInt(n / 2, 10)) + 1; return 0;}// Generating the first 'n' terms // of Moser-de Bruijn Sequencefunction moserDeBruijn(n){ for(let i = 0; i < n; i++) document.write(gen(i) + " "); document.write("</br>");}// Driver codelet n = 15;document.write("First " + n + " terms of " + "Moser-de Bruijn Sequence : " + "</br>");moserDeBruijn(n);// This code is contributed by decode2207</script> |
Output :
First 15 terms of Moser-de Bruijn Sequence : 0 1 4 5 16 17 20 21 64 65 68 69 80 81 84
Time complexity: O(log2n)
Auxiliary Space: O(1)
Dynamic Programming Implementation:
C++
// CPP code to generate first 'n' terms // of the Moser-de Bruijn Sequence#include <bits/stdc++.h>using namespace std;// Function to generate nth term // of Moser-de Bruijn Sequenceint gen(int n){ int S[n+1]; S[0] = 0; S[1] = 1; for (int i = 2; i <= n; i++) { // S(2 * n) = 4 * S(n) if (i % 2 == 0) S[i] = 4 * S[i / 2]; // S(2 * n + 1) = 4 * S(n) + 1 else S[i] = 4 * S[i / 2] + 1; } return S[n];}// Generating the first 'n' terms // of Moser-de Bruijn Sequencevoid moserDeBruijn(int n){ for (int i = 0; i < n; i++) cout << gen(i) << " "; cout << "\n";}// Driver Codeint main(){ int n = 15; cout << "First " << n << " terms of " << "Moser-de Bruijn Sequence : \n"; moserDeBruijn(n); return 0;} |
Java
// Java code to generate first 'n' terms // of the Moser-de Bruijn Sequenceclass GFG { // Function to generate nth term // of Moser-de Bruijn Sequencestatic int gen(int n){ int []S = new int [n + 1]; S[0] = 0; if(n != 0) S[1] = 1; for (int i = 2; i <= n; i++) { // S(2 * n) = 4 * S(n) if (i % 2 == 0) S[i] = 4 * S[i / 2]; // S(2 * n + 1) = 4 * S(n) + 1 else S[i] = 4 * S[i/2] + 1; } return S[n];}// Generating the first 'n' terms // of Moser-de Bruijn Sequencestatic void moserDeBruijn(int n){ for (int i = 0; i < n; i++) System.out.print(gen(i)+" ");}// Driver Codepublic static void main(String[] args){ int n = 15; System.out.println("First " + n + " terms of " + "Moser-de Bruijn Sequence : "); moserDeBruijn(n);}}// This code is contributed by // Smitha Dinesh Semwal. |
Python3
# python3 code to generate first 'n' terms # of the Moser-de Bruijn Sequence# Function to generate nth term # of Moser-de Bruijn Sequencedef gen( n ): S = [0, 1] for i in range(2, n+1): # S(2 * n) = 4 * S(n) if i % 2 == 0: S.append(4 * S[int(i / 2)]); # S(2 * n + 1) = 4 * S(n) + 1 else: S.append(4 * S[int(i / 2)] + 1); z = S[n]; return z;# Generating the first 'n' terms # of Moser-de Bruijn Sequencedef moserDeBruijn(n): for i in range(n): print(gen(i), end = " ")# Driver Coden = 15print("First", n, "terms of ", "Moser-de Brujn Sequence:")moserDeBruijn(n)# This code is contributed by mits. |
C#
// C# code to generate first 'n' terms // of the Moser-de Bruijn Sequenceusing System;class GFG { // Function to generate nth term // of Moser-de Bruijn Sequencestatic int gen(int n){ int []S = new int [n + 1]; S[0] = 0; if(n != 0) S[1] = 1; for (int i = 2; i <= n; i++) { // S(2 * n) = 4 * S(n) if (i % 2 == 0) S[i] = 4 * S[i / 2]; // S(2 * n + 1) = 4 * S(n) + 1 else S[i] = 4 * S[i/2] + 1; } return S[n];}// Generating the first 'n' terms // of Moser-de Bruijn Sequencestatic void moserDeBruijn(int n){ for (int i = 0; i < n; i++) Console.Write(gen(i)+" ");}// Driver Codepublic static void Main(){ int n = 15; Console.WriteLine("First " + n + " terms of " + "Moser-de Bruijn Sequence : "); moserDeBruijn(n);}}// This code is contributed by // Smitha Dinesh Semwal. |
PHP
<?php// PHP code to generate first 'n' terms // of the Moser-de Bruijn Sequence// Function to generate nth term // of Moser-de Bruijn Sequencefunction gen( $n){ $S = array(); $S[0] = 0; $S[1] = 1; for ( $i = 2; $i <= $n; $i++) { // S(2 * n) = 4 * S(n) if ($i % 2 == 0) $S[$i] = 4 * $S[$i / 2]; // S(2 * n + 1) = 4 * S(n) + 1 else $S[$i] = 4 * $S[$i/2] + 1; } return $S[$n];}// Generating the first 'n' terms // of Moser-de Bruijn Sequencefunction moserDeBruijn( $n){ for ( $i = 0; $i < $n; $i++) echo gen($i) , " "; echo "\n";}// Driver Code$n = 15;echo "First " ,$n ," terms of " , "Moser-de Bruijn Sequence : \n";moserDeBruijn($n);// This code is contributed by anuj_67.?> |
Javascript
<script> // Javascript code to generate first 'n' terms // of the Moser-de Bruijn Sequence // Function to generate nth term // of Moser-de Bruijn Sequence function gen(n) { let S = new Array(n + 1); S.fill(0); S[0] = 0; if(n != 0) S[1] = 1; for (let i = 2; i <= n; i++) { // S(2 * n) = 4 * S(n) if (i % 2 == 0) S[i] = 4 * S[parseInt(i / 2, 10)]; // S(2 * n + 1) = 4 * S(n) + 1 else S[i] = 4 * S[parseInt(i / 2, 10)] + 1; } return S[n]; } // Generating the first 'n' terms // of Moser-de Bruijn Sequence function moserDeBruijn(n) { for (let i = 0; i < n; i++) document.write(gen(i)+" "); } let n = 15; document.write("First " + n + " terms of " + "Moser-de Bruijn Sequence : " + "</br>"); moserDeBruijn(n);</script> |
Output :
First 15 terms of Moser-de Bruijn Sequence : 0 1 4 5 16 17 20 21 64 65 68 69 80 81 84
Time complexity: O(n) since using a for loop
Auxiliary Space: O(n) for array
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
