मान लीजिए कि हमारे पास एक धनात्मक पूर्णांक x है, हम x (op1) x (op2) x (op3) x ... के रूप का व्यंजक लिखेंगे, जहां op1, op2, आदि संचालिका हैं। और ये ऑपरेटर या तो जोड़, घटाव, गुणा या भाग हो सकते हैं। उदाहरण के लिए, x =3 के साथ, हम 3 * 3 / 3 + 3 - 3 लिख सकते हैं जो कि 3 का मान है। कुछ नियम हैं, ये इस प्रकार हैं -
-
विभाजन संचालिका (/) परिमेय संख्याएँ लौटाता है।
-
कहीं भी कोई कोष्ठक नहीं रखा गया है।
-
हम संचालन के सामान्य क्रम का उपयोग करते हैं - गुणा और भाग में जोड़ और घटाव की तुलना में उच्च प्राथमिकता होती है।
-
यूनरी नेगेशन ऑपरेटर की अनुमति नहीं है।
हमें कम से कम ऑपरेटरों के साथ एक अभिव्यक्ति लिखनी है जैसे कि अभिव्यक्ति दिए गए लक्ष्य के बराबर है। इसलिए, हम ऑपरेटरों की सबसे कम संख्या पाएंगे।
इसलिए, यदि इनपुट x =4, लक्ष्य =15 जैसा है, तो आउटपुट 3 होगा, क्योंकि हम 15 को 4*4- 4/4
के रूप में व्यक्त कर सकते हैं।इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
यदि लक्ष्य x के समान है, तो -
-
यदि x> लक्ष्य है, तो −
-
कम से कम (x - लक्ष्य) * 2 और (लक्ष्य * 2) - 1
-
-
-
योग:=एक्स, टी:=0
-
जबकि योग <लक्ष्य, करें -
-
योग :=योग * x
-
(टी 1 से बढ़ाएँ)
-
-
यदि योग लक्ष्य के समान है, तो -
-
वापसी टी
-
-
एल:=इंफ, आर:=इंफ
-
यदि योग - लक्ष्य लक्ष्य, तो -
-
r :=कम से कमOpsExpressTarget(x, योग - लक्ष्य)
-
-
एल :=कम से कमOpsExpressTarget(x, लक्ष्य - (योग / 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