# Find nth element of Stern’s Diatomic Series in C++

In this article, we will learn how to find the nth element of Stern’s Diatomic Series in C++.

Stern’s Diatomic Series is a sequence 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5 …. which emerges in the Calkin-Wilf tree. It is in some cases otherwise called the fusc function.

In mathematical notation, the nth term can be given by recurrence equation

s(n) = s(n/2)                                             for n even

s(n) = s((n-1)/2)+ s((n+1)/2)                for n odd

where s(0) = 0, s(1) = 1

## Stern’s Diatomic Series in C++

We are going to solve this problem using dynamic programming.

1. Create a dynamic array of size n+1. Initialize the dp to 0 and do to 1.

2. Iterate the array for range (2, n)

• If n is even then set dp[i] = dp[i/2].
• Else set dp[i] = dp[(i-1)/2]+dp[(i+1)/2]

3. Finally, return dp[n].

```#include <bits/stdc++.h>
using namespace std;
int Sterns_Diatomic_Series(int n){
int dp[n+1];
dp = 0;
dp = 1;
for(int i=2;i<=n;i++){
if (i%2 == 0)
dp[i] = dp[i/2];
else
dp[i] = dp[(i-1)/2]+dp[(i+1)/2];
}
return dp[n];
}
int main(){
int n;
cout<<"Enter the n value: ";
cin>>n;
cout<<"The nth element of Sterns Diatomic Series is "<<Sterns_Diatomic_Series(n);
return 0;
}```

Output

```Enter the n value: 20
The nth element of Sterns Diatomic Series is 3

Enter the n value: 15
The nth element of Sterns Diatomic Series is 4```