मान लीजिए हमारे पास एक सरणी nums और एक संख्या है। हम सरणी में तत्व जोड़ सकते हैं, जैसे कि रेंज [1, n] (दोनों समावेशी) में कोई भी संख्या सरणी में कुछ तत्वों के योग द्वारा बनाई जा सकती है। हमें आवश्यक पैच की न्यूनतम संख्या ढूंढनी है। तो जब सरणी [1,4] जैसी है और दी गई संख्या n = 7 है, तो आउटपुट 1 होगा, क्योंकि प्रारंभ में nums [1], [4] और [1,4] = 5 हैं, अब यदि हम सरणी में 2 जोड़ते हैं, तो nums [1], [2], [4], [1,2], [1,4],[2,4], [1,2,4] होंगे, इसलिए योग मान क्रमशः 1, 2, 4, 3, 5, 6, 7 होंगे।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
req := 1, i := 0, ret := 0
जब req <= n, करें -
यदि i < nums का आकार और nums[i] <= req, तो,
req = req + nums[i]
i को 1 से बढ़ाएं
अन्यथा
req = req + req
ret को 1 से बढ़ाएं
ret लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h> using namespace std; class Solution { public: int minPatches(vector<int>& nums, int n) { long long int req = 1; int i = 0; int ret = 0; while(req <= n){ if(i < nums.size() && nums[i] <= req){ req += nums[i]; i++; } else { req += req; ret++; } } return ret; } }; main(){ Solution ob; vector<int> v = {1,4}; cout << (ob.minPatches(v, 7)); }इनपुट
{1,4}आउटपुट
1
