# 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[0] to 0 and do[1] 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] = 0; dp[1] = 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

Also, read

## Leave a Reply