Dragon Curve Sequence is an infinite binary sequence of 0’s and 1’s. The first term of the sequence is 1.
From the next term, we alternately insert 1 and 0 between each element of the previous term.
To understand better refer the following explanations:
- 1 (starts with 1)
- “1” 1 “0”
1 and 0 are inserted alternately to the left and right of the previous term. Here the number in the double quotes represents the newly added elements.
So the second term becomes
1 1 0- “1” 1 “0” 1 “1” 0 “0”
So the third term becomes
1 1 0 1 1 0 0
- “1” 1 “0” 1 “1” 0 “0” 1 “1” 1 “0” 0 “1” 0 “0”
The fourth term becomes
1 1 0 1 1 0 0 1 1 1 0 0 1 0 0
This is also popularly known as the regular paperfolding sequence. Given a natural number n, the task is to find the nth string formed by Dragon Curve sequence of length 
.
Examples:
Input: n = 4 Output: 110110011100100 Explanation: We get 1 as the first term, "110" as the second term, "1101100" as the third term , And hence our fourth term will be "110110011100100" Input: n = 3 Output: 1101100
Approach:
- Step 1: Start with the first term 1. Then add 1 and 0 alternately after each element of the preceding term.
- Step 2: The new term obtained becomes the current term.
- Step 3: Repeat the process in a loop from 1 to n, to generate each term and finally the nth term.
Algorithm :
- Step 1: Take the input size n
- Step 2: Initialize 1st term of string as “1”.
- step 3: generate each term of the sequence using nested for loop.
- Step 4: Add alternate 0 and 1 in between, if previous term is 1 then add 0; vice versa.
- Step 5: Print the output string.
Below is the implementation of above idea:
C++
// CPP code to find nth term// of the Dragon Curve Sequence#include <bits/stdc++.h>using namespace std;// function to generate the nth termstring Dragon_Curve_Sequence(int n) { // first term string s = "1"; // generating each term of the sequence for (int i = 2; i <= n; i++) { string temp = "1"; char prev = '1', zero = '0', one = '1'; // loop to generate the ith term for (int j = 0; j < s.length(); j++) { // add character from the // original string temp += s[j]; // add alternate 0 and 1 in between if (prev == '0') { // if previous added term // was '0' then add '1' temp += one; // now current term becomes // previous term prev = one; } else { // if previous added term // was '1', then add '0' temp += zero; // now current term becomes // previous term prev = zero; } } // s becomes the ith term of the sequence s = temp; } return s;}// Driver programint main(){ // Taking inputs int n = 4; // generate nth term of dragon curve sequence string s = Dragon_Curve_Sequence(n); // Printing output cout << s << "\n";} |
Java
// Java code to find nth term// of the Dragon Curve Sequenceimport java.util.*;class solution{// function to generate the nth termstatic String Dragon_Curve_Sequence(int n) { // first term String s = "1"; // generating each term of the sequence for (int i = 2; i <= n; i++) { String temp = "1"; char prev = '1', zero = '0', one = '1'; // loop to generate the ith term for (int j = 0; j < s.length(); j++) { // add character from the // original string temp += s.charAt(j); // add alternate 0 and 1 in between if (prev == '0') { // if previous added term // was '0' then add '1' temp += one; // now current term becomes // previous term prev = one; } else { // if previous added term // was '1', then add '0' temp += zero; // now current term becomes // previous term prev = zero; } } // s becomes the ith term of the sequence s = temp; } return s;}// Driver programpublic static void main(String args[]){ // Taking inputs int n = 4; // generate nth term of dragon curve sequence String s = Dragon_Curve_Sequence(n); // Printing output System.out.println(s);}}//This code is contributed by //Surendra_Gangwar |
Python
# Python code to find nth term# of the Dragon Curve Sequence# function to generate # the nth termdef Dragon_Curve_Sequence(n): # first term s = "1" # generating each term # of the sequence for i in range(2, n + 1): temp = "1" prev = '1' zero = '0' one = '1' # loop to generate the ith term for j in range(len(s)): # add character from the # original string temp += s[j] # add alternate 0 and # 1 in between if (prev == '0'): # if previous added term # was '0' then add '1' temp += one # now current term becomes # previous term prev = one else: # if previous added term # was '1', then add '0' temp += zero # now current term becomes # previous term prev = zero # s becomes the ith term # of the sequence s = temp return s# Driver Coden = 4# generate nth term of # dragon curve sequences = Dragon_Curve_Sequence(n)# Printing outputprint(s)# This code is contributed by# Sanjit_Prasad |
C#
// C# code to find nth term // of the Dragon Curve Sequence using System;class GFG{ // function to generate the nth term static String Dragon_Curve_Sequence(int n) { // first term String s = "1"; // generating each term of the sequence for (int i = 2; i <= n; i++) { String temp = "1"; char prev = '1', zero = '0', one = '1'; // loop to generate the ith term for (int j = 0; j < s.Length; j++) { // add character from the // original string temp += s[j]; // add alternate 0 and 1 in between if (prev == '0') { // if previous added term // was '0' then add '1' temp += one; // now current term becomes // previous term prev = one; } else { // if previous added term // was '1', then add '0' temp += zero; // now current term becomes // previous term prev = zero; } } // s becomes the ith term of the sequence s = temp; } return s; } // Driver Codepublic static void Main() { // Taking inputs int n = 4; // generate nth term of dragon // curve sequence String s = Dragon_Curve_Sequence(n); // Printing output Console.WriteLine(s); } } // This code is contributed by Rajput-Ji |
PHP
<?php// PHP code to find nth term// of the Dragon Curve Sequence// function to generate the nth termfunction Dragon_Curve_Sequence($n) { // first term $s = "1"; // generating each term of the sequence for ($i = 2; $i <= $n; $i++) { $temp = "1"; $prev = '1'; $zero = '0'; $one = '1'; // loop to generate the ith term for ($j = 0; $j < strlen($s); $j++) { // add character from the // original string $temp .= $s[$j]; // add alternate 0 and 1 in between if ($prev == '0') { // if previous added term // was '0' then add '1' $temp .= $one; // now current term becomes // previous term $prev = $one; } else { // if previous added term // was '1', then add '0' $temp .= $zero; // now current term becomes // previous term $prev = $zero; } } // s becomes the ith term of the sequence $s = $temp; } return $s;}// Driver code // Taking inputs $n = 4; // generate nth term of dragon curve sequence $s = Dragon_Curve_Sequence($n); // Printing output echo $s."\n";// This code is contributed by mits?> |
Javascript
<script>// Javascript code to find nth term// of the Dragon Curve Sequence// function to generate the nth termfunction Dragon_Curve_Sequence(n) { // first term let s = "1"; // generating each term of the sequence for (let i = 2; i <= n; i++) { let temp = "1"; let prev = '1'; let zero = '0'; let one = '1'; // loop to generate the ith term for (let j = 0; j < s.length; j++) { // add character from the // original string temp = temp + s[j]; // add alternate 0 and 1 in between if (prev == '0') { // if previous added term // was '0' then add '1' temp += one; // now current term becomes // previous term prev = one; } else { // if previous added term // was '1', then add '0' temp += zero; // now current term becomes // previous term prev = zero; } } // s becomes the ith term of the sequence s = temp; } return s;}// Driver code // Taking inputs let n = 4; // generate nth term of dragon curve sequence let s = Dragon_Curve_Sequence(n); // Printing output document.write(s + "<br>");// This code is contributed by gfgking</script> |
Output:
110110011100100
Complexity Analysis:
- Time Complexity: O(n*s) where s is the length of resultant string
- Auxiliary Space: O(s) where s is the length of resultant string
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!
