Recursive function 1#10296

Recursive function 1 (Editorial)

Due to the limitation of $n \leq 1 0^{18}$ n \le 10^{18}, it is impossible to use a linear array to store the results of the function $f$ . Therefore, we'll use a map data structure.

Example

Consider the process of computing the function for $n = 5$ n = 5:

Algorithm realization

Declare a map $m$ to store the function values: $m [n] = f (n)$ m[n] = f(n).

map<long long, long long> m;

Implement the function f.

long long f(long long n)
{
  if (n == 0) return 1;
  if (m.count(n) > 0) return m[n];
  return m[n] = f(n / 2) + f(n / 3);
}

The main part of the program. Read the input value of $n$ . Compute and print the value of the function $f (n)$ .

scanf("%lld", &n);
res = f(n);
printf("%lld\n", res);

Java realization

import java.util.*;

public class Main
{
  static Map<Long, Long> m = new HashMap<Long, Long>();
  static long n;
  
  public static long f(long n)
  {
    if (n == 0) return 1;
    if (m.containsKey(n)) return m.get(n);
    long res = f(n/2) + f(n/3);
    m.put(n,res);
    return res;
  }
  
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    n = con.nextLong(); 
    System.out.println(f(n));
    con.close();
  }
}

Java

Python realization

Declare a vocabulary $m$ to store the function values: $m [n] = f (n)$ m[n] = f(n).

m = {}

Implement the function f.

def f(n):
  if n == 0:
    return 1
  if n in m:
    return m[n]
  m[n] = f(n // 2) + f(n // 3)
  return m[n]

Python

The main part of the program. Read the input value of $n$ . Compute and print the value of the function $f (n)$ .

n = int(input())
res = f(n)
print(res)