मान लीजिए हमारे पास एक धनात्मक पूर्णांक x है, हम x (op1) x (op2) x (op3) x ... के रूप में एक अभिव्यक्ति लिखेंगे जहां op1, op2, आदि ऑपरेटर हैं। ये ऑपरेटर जोड़, घटाव, गुणा, या भाग हो सकते हैं। कुछ नियम हैं:
भाग ऑपरेटर (/) परिमेय संख्याएं लौटाता है
कहीं भी कोष्ठक नहीं रखे जाते
हम ऑपरेशन के सामान्य क्रम का उपयोग करते हैं - गुणा और भाग की प्राथमिकता जोड़ और घटाव से अधिक होती है
यूनरी निगेशन ऑपरेटर अनुमत नहीं है
हमें दिए गए लक्ष्य के बराबर अभिव्यक्ति लिखने के लिए ऑपरेटरों की न्यूनतम संख्या ढूंढनी है।
उदाहरण के लिए, यदि x = 4, लक्ष्य = 15, तो आउटपुट 3 होगा, क्योंकि हम 15 को 4*4 - 4/4 के रूप में व्यक्त कर सकते हैं।
हल करने का दृष्टिकोण
हम x की घातों के आधार पर एक लालची पुनरावर्ती दृष्टिकोण का उपयोग करते हैं:
यदि लक्ष्य == x, तो 0 ऑपरेटर चाहिए
यदि x > लक्ष्य, तो min((x-target)*2, target*2-1) वापस करें
x की घातों को तब तक गुणा करें जब तक sum >= लक्ष्य
यदि sum == लक्ष्य, तो उपयोग की गई घातें वापस करें
अन्यथा, दो विकल्पों पर पुनरावर्ती करें: sum - लक्ष्य और लक्ष्य - sum/x
न्यूनतम लें और 1 जोड़ें
उदाहरण
#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;
}
};
int main(){
Solution ob;
cout << (ob.leastOpsExpressTarget(4, 15));
return 0;
}
इनपुट
4, 15
आउटपुट
3
