ধরুন আমাদের একটি ধনাত্মক পূর্ণসংখ্যা x আছে, আমরা x (op1) x (op2) x (op3) x... যেখানে op1, op2 ইত্যাদি অপারেটর হবে তার একটি এক্সপ্রেশন লিখব। এবং এই অপারেটরগুলি যোগ, বিয়োগ, গুণ বা ভাগ হতে পারে। উদাহরণস্বরূপ, x =3 দিয়ে, আমরা 3 * 3 / 3 + 3 - 3 লিখতে পারি যা 3 এর মান। কিছু কিছু নিয়ম আছে, সেগুলি নিম্নরূপ -
-
বিভাগ অপারেটর (/) মূলদ সংখ্যা প্রদান করে।
-
কোথাও কোন বন্ধনী রাখা নেই।
-
আমরা ক্রিয়াকলাপের স্বাভাবিক ক্রম ব্যবহার করি - যোগ এবং বিয়োগের চেয়ে গুণ এবং ভাগের অগ্রাধিকার বেশি।
-
Unary negation অপারেটর অনুমোদিত নয়৷
আমাদের সর্বনিম্ন সংখ্যক অপারেটর সহ একটি অভিব্যক্তি লিখতে হবে যাতে অভিব্যক্তিটি প্রদত্ত লক্ষ্যের সমান হয়। সুতরাং, আমরা সর্বনিম্ন সংখ্যক অপারেটর খুঁজে পাব।
সুতরাং, ইনপুট যদি x =4, টার্গেট =15 এর মত হয়, তাহলে আউটপুট হবে 3, যেমন আমরা 15 কে 4*4- 4/4 হিসাবে প্রকাশ করতে পারি
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
যদি লক্ষ্য x এর মত হয়, তাহলে −
-
যদি x> টার্গেট হয়, তাহলে −
-
সর্বনিম্ন ফেরত দিন (x - লক্ষ্য) * 2 এবং (লক্ষ্য * 2) - 1
-
-
-
যোগফল :=x, t :=0
-
সমষ্টি
-
যোগফল :=যোগফল * x
-
(t 1 দ্বারা বাড়ান)
-
-
যদি যোগফল টার্গেটের সমান হয়, তাহলে −
-
টি
ফেরত দিন
-
-
l :=inf, r :=inf
-
যদি যোগফল - লক্ষ্য লক্ষ্য, তারপর −
-
r :=leastOpsExpressTarget(x, sum - target)
-
-
l :=leastOpsExpressTarget(x, target - (sum/x))
-
1 + সর্বনিম্ন l এবং r
ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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;
int 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;
}
};
main(){
Solution ob;
cout << (ob.leastOpsExpressTarget(4, 15));
} ইনপুট
4, 15
আউটপুট
3
