# Find nth term of the Dragon Curve Sequence

**Dragon Curve Sequence** is an infinite binary sequence of 0s and 1s. 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:**

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

Input: n = 4 Output: 110110011100100Explanation: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:** Start with the first term 1. Then add 1 and 0 alternately after each element of the preceding term. The new term obtained becomes the current term. Repeat the process in a loop from 1 to n to generate each term and finally the nth term.

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 term` `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 program` `int` `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 Sequence` `import` `java.util.*;` ` ` `class` `solution` `{` ` ` `// 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.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 program` `public` `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 term` `def` `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 Code` `n ` `=` `4` ` ` `# generate nth term of ` `# dragon curve sequence` `s ` `=` `Dragon_Curve_Sequence(n)` ` ` `# Printing output` `print` `(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 Code` `public` `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 term` `function` `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 term` `function` `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