সি++-এ n কে ০ করার ন্যূনতম অপারেশন সংখ্যা গণনা

সমস্যা বিবরণ

একটি সংখ্যা n দেওয়া আছে। তিনটি অপারেশন করতে পারেন:

1. n = n - 1
2. যদি n সম হয়: n = n - n/2
3. যদি n ৩ দিয়ে বিভাজ্য হয়: n = n - 2*(n/3)

উদাহরণ: n = 16 → আউটপুট 5 (৪বার n/2 কমিয়ে ১, তারপর ১ কমিয়ে ০)।

সমাধানের পদ্ধতি

ডাইনামিক প্রোগ্রামিং + মেমোইজেশন (রিকার্শন):

1. dp[x] = x কে ০ করার ন্যূনতম অপারেশন।
2. বেস কেস: x <= 0 → 0, x == 1 → 1।
3. ট্রানজিশন:
   • md2 = x % 2, md3 = x % 3
   • ret = min(x, md2 + 1 + dfs((x-md2)/2), md3 + 1 + dfs((x-md3)/3))
4. মেমোইজেশন দিয়ে পুনরাবৃত্তি এড়ান।

উদাহরণ কোড

#include <bits/stdc++.h>
using namespace std;

unordered_map<int, int> dp;

int dfs(int x) {
    int ret = x;
    if (dp.count(x)) return dp[x];
    if (x <= 0) return x;
    if (x == 1) return 1;
    int md2 = x % 2;
    int md3 = x % 3;
    ret = min({ret, md2 + 1 + dfs((x - md2) / 2), md3 + 1 + dfs((x - md3) / 3)});
    return dp[x] = ret;
}

int solve(int n) { return dfs(n); }

int main() {
    int n = 16;
    cout << solve(n);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: 16

আউটপুট: 5