Untitled

 avatar
unknown
plain_text
2 months ago
817 B
1
Indexable
#include <bits/stdc++.h>
using namespace std;

// We'll memoize f(n) in a hash map to avoid recomputing.
unordered_map<long long, long long> memo;

// Define the function f(n) recursively with memoization.
long long f(long long n) {
    // Base case:
    if (n == 0) {
        return 1;
    }
    // If we already computed f(n), return it from the memo table.
    if (memo.count(n)) {
        return memo[n];
    }
    // Recurrence: f(n) = f(n/2) + f(n/3) for n > 0.
    long long result = f(n / 2) + f(n / 3);

    // Store in memo before returning.
    memo[n] = result;
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n;
    cin >> n;       // Read the (potentially large) input
    cout << f(n) << "\n";  
    return 0;
}
Editor is loading...
Leave a Comment