C++-এ সংখ্যা প্রকাশের জন্য ন্যূনতম অপারেটর

সমস্যা বিবরণ

একটি ধনাত্মক পূর্ণসংখ্যা x দেওয়া থাকলে, x (op1) x (op2) x ... রূপে এক্সপ্রেশন লিখতে হবে যাতে মান target হয়। অপারেটরগুলো +, -, *, / হতে পারে (সাধারণ অপারেটর প্রেসিডেন্স)। ন্যূনতম অপারেটর সংখ্যা বের করতে হবে।

উদাহরণ

x = 4, target = 15 → আউটপুট = 3 (এক্সপ্রেশন: 4*4 - 4/4)

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

• রিকার্সিভGreedy পদ্ধতি ব্যবহার করা হয়।
• x এর ঘাতগুলো দিয়ে target-এর নিকটতম মান বের করা হয়।
• লেফট এবং রাইট রিকার্শন দিয়ে ন্যূনতম অপারেটর গণনা করা হয়।
• বেস কেস: target == x → 0 অপারেটর।

C++ বাস্তবায়ন

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

class Solution {
public:
    int leastOpsExpressTarget(int x, int target) {
        if (target == x) return 0;
        if (x > target)
            return min((x - target) * 2, (target * 2) - 1);
        
        lli sum = x;
        int t = 0;
        while (sum < target) {
            sum *= x;
            t++;
        }
        if (sum == target) return t;
        
        int l = INT_MAX, r = INT_MAX;
        if (sum - target < target)
            r = leastOpsExpressTarget(x, sum - target) + t;
        l = leastOpsExpressTarget(x, target - (sum / x)) + t - 1;
        
        return min(l, r) + 1;
    }
};

int main() {
    Solution ob;
    cout << ob.leastOpsExpressTarget(4, 15);
    return 0;
}

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

ইনপুট: 4, 15

আউটপুট: 3