Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में थ्रेशहोल्ड दिए जाने पर सबसे छोटा भाजक ढूंढना


मान लीजिए हमारे पास nums नामक पूर्णांकों की एक सरणी और एक पूर्णांक k है, जो थ्रेशहोल्ड मान है, हम एक धनात्मक पूर्णांक भाजक चुनेंगे और सभी सरणी को इससे विभाजित करेंगे और विभाजन के परिणाम को जोड़ेंगे। हमें सबसे छोटा भाजक ढूंढना है जैसे कि ऊपर उल्लिखित परिणाम थ्रेशहोल्ड मान k से कम या बराबर हो। उदाहरण के लिए: यदि nums = [1,2,5,9] और k = 6, तो आउटपुट 5 होगा। हम भाजक 1 होने पर योग (1+2+5+9) = 17 प्राप्त कर सकते हैं। यदि भाजक 4 है, तो हम योग 7 प्राप्त कर सकते हैं जैसे (1+1+2+3), जब भाजक 5 है, तो योग (1+1+1+2) = 5 होगा।

यह गारंटी है कि एक उत्तर होगा।

हल का दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

  • check नामक एक विधि परिभाषित करें, यह तीन पैरामीटर लेगी जैसे x, सरणी nums, और k, यह निम्नानुसार होगी:
    • sum := 0
    • i = 0 से nums का आकार - 1 तक:
      • sum := sum + nums[i] / x की सीलिंग मान
    • यदि sum <= k तो true लौटाएं, अन्यथा false
  • वास्तविक विधि इस प्रकार होगी:
    • low := 1 और high := inf सेट करें
    • while low < high:
      • mid := low + (high - low)/2
      • यदि check(mid, nums, k), तो high := mid, अन्यथा low := mid + 1
    • high लौटाएं

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    bool ok(int x, vector<int> &nums, int th){ 
        int sum = 0; 
        for(int i = 0; i < nums.size(); i++){ 
            sum += ceil((double)nums[i] / (double)x); 
        } 
        return sum <= th; 
    } 
    int smallestDivisor(vector<int>& nums, int th) { 
        int low = 1; 
        int high = 1e7; 
        while(low < high){ 
            int mid = low + (high - low) / 2; 
            if(ok(mid, nums, th)){ 
                high = mid; 
            } else low = mid + 1; 
        } 
        return high; 
    } 
}; 

int main(){ 
    vector<int> v = {1,2,5,9}; 
    Solution ob; 
    cout << (ob.smallestDivisor(v, 6)); 
}

इनपुट

[1,2,5,9] 6

आउटपुट

5

  1. C++ में थ्रेशोल्ड दूरी पर सबसे कम पड़ोसियों वाला शहर ढूंढना C++ में थ्रेशोल्ड दूरी पर सबसे कम पड़ोसियों वाला शहर ढूंढना

    मान लीजिए n शहर हैं जो 0 से n-1 तक नंबरेड हैं। अगर हमारे पास ऐरे edges है जहां edges[i] = [fromi, toi, weighti] शहरों fromi और toi के बीच एक बाईडायरेक्शनल और वेटेड एज दर्शाता है, और दिया गया इंटीजर distanceThreshold है। हमें वह शहर ढूंढना है जिसमें उन शहरों की सबसे कम संख्या हो जो किसी पथ के माध्यम

  1. - C++ में दिए गए सूचकांकों के साथ N फाइबोनैचि संख्याओं का GCD ढूंढना

    यहां हमें दिए गए सूचकांकों के साथ n फाइबोनैचि पदों का GCD ढूंढना है। तो सबसे पहले हमें अधिकतम सूचकांक प्राप्त करना होगा, और फाइबोनैचि पद उत्पन्न करने होंगे। कुछ फाइबोनैचि पद ऐसे हैं: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... सूचकांक 0 से शुरू होता है। तो 0वें सूचकांक पर तत्व 0 है। यदि हमें सूचकांकों {2,

  1. - C++ प्रोग्राम: दी गई सीक्वेंस का लॉन्गेस्ट इन्क्रीजिंग सबसीक्वेंस ढूंढना

    लॉन्गेस्ट इन्क्रीजिंग सबसीक्वेंस (LIS) एक ऐसा सबसीक्वेंस होता है जहां प्रत्येक एलिमेंट अपने पिछले एलिमेंट से बड़ा होता है। यहां हम पूर्णांकों के एक सेट से लॉन्गेस्ट इन्क्रीजिंग सबसीक्वेंस की लंबाई ढूंढने का प्रयास करेंगे। इनपुट: पूर्णांकों का सेट {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 1