CodingGyan

Stern's Diatomic Sequence

medium Series and Sequences

Problem

Stern's diatomic sequence is defined by a(0) = 0, a(1) = 1, a(2k) = a(k) and a(2k + 1) = a(k) + a(k + 1). It starts 0, 1, 1, 2, 1, 3, 2, 3, 1, 4, ... Print a(n).

Constraints

  • 0 <= n <= 10^5

Examples

Input

7

Output

3

Input

9

Output

4

Solutions

Best approachTime O(n)Space O(n)

Every term depends on terms with smaller indexes, so a table from 0 up to n can be filled in order. It uses O(n) time and memory.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Find a(n).
 * Input   : n.
 * Output  : a(n).
 * Approach: Table
 * Time    : O(n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static long solve(long n) {
        // Step 1: A table of the terms from 0 up to n. The two start terms are given.
        int size = (int) n;
        long[] terms = new long[Math.max(size + 2, 2)];
        terms[1] = 1;
        // Step 2: Each term uses one or two earlier terms, which are already in the table.
        for (int i = 2; i <= size; i++) {
            terms[i] = i % 2 == 0 ? terms[i / 2] : terms[i / 2] + terms[i / 2 + 1];
        }
        return terms[size];
    }

    public static void main(String[] args) {
        long n = new Scanner(System.in).nextLong();
        System.out.println(solve(n));
    }
}
Hints (1)
  1. Which terms does a(2k + 1) need?

Try these next