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

• Print Fibonacci series in C++
• How to print Lucas series in C++
• Longest Common Substring in C++ using dynamic programming