एक थ्रेसहोल्ड Leetcode समाधान दिया गया सबसे छोटा विभाजक ढूंढें  


कठिनाई स्तर मध्यम
में अक्सर पूछा ऐप डायनामिक्स गूगल एसएपी वॉलमार्ट लैब्स
एल्गोरिदम कोडिंग साक्षात्कार साक्षात्कार की तैयारी लेटकोड लेटकोड सॉल्यूशंस

यह पोस्ट थ्रेशोल्ड लेटेकोड सॉल्यूशन दिए गए फाइंड के सबसे छोटे डिवाइडर पर है

समस्या का विवरण  

समस्या में "थ्रेशोल्ड दिए गए सबसे छोटे भाजक को ढूंढें" हमें एक अंक सरणी और एक दहलीज मान दिया जाता है। एक चर "परिणाम" को सभी उत्तरों के योग के रूप में परिभाषित किया जाता है जब सरणी में तत्वों को एक भाजक द्वारा विभाजित किया जाता है। हमारा कार्य विभाजक के सबसे छोटे संभव मान को इस तरह से खोजना है कि परिणाम थ्रेशोल्ड से अधिक या उसके बराबर हो।

जब हम एक भाजक द्वारा सरणी में तत्वों को विभाजित करते हैं, तो हम विभाजन के उत्तर के रूप में छत के मूल्य पर विचार कर रहे हैं। विभाजक होना चाहिए a सकारात्मक पूर्णांक.

उदाहरण  

arr=[1,2,5,9], threshold=6
5

स्पष्टीकरण: जब हम सभी तत्वों को 1 परिणाम से विभाजित करते हैं (1 + 2 + 5 + 9) 17 जो कि 6 से अधिक है। इसलिए, हम परिणाम के मूल्य को कम करने के लिए भाजक के मूल्य में वृद्धि करेंगे।

अब यदि हम भाजक = ४ मानते हैं तो परिणाम १ (१ + १ + २ + ३), है, जो ६. से अधिक है, इसलिए हम परिणाम के मूल्य को कम करने के लिए भाजक के मान को बढ़ाएंगे।

यदि हम भाजक = ५ मानते हैं तो परिणाम (१ + १ + १ + २) ६ है। अतः उत्तर ५ है।

दृष्टिकोण  

हमारा काम खोजने के लिए है न्यूनतम मान भाजक का। तो, आइए पहले सोचते हैं कि क्या हो सकता है न्यूनतम और अधिकतम भाजक का मान।

  • भाजक का न्यूनतम मान 1 है क्योंकि भाजक धनात्मक पूर्णांक है।
  • विभाजक के अधिकतम मूल्य के बारे में बात करते हुए हम इसे अंक सरणी में अधिकतम मूल्य पर ट्रिम कर सकते हैं क्योंकि इससे अधिक मूल्य भी हमेशा एक ही उत्तर देगा।
यह भी देखें
K Weakest Rows in a Matrix Leetcode Solution

एक थ्रेसहोल्ड Leetcode समाधान को देखते हुए सबसे छोटा विभाजक खोजेंपिन

  • अब हमारे पास है न्यूनतम और अधिकतम हमारे हाथ में भाजक का मूल्य। अब हमारा एकमात्र कार्य सबसे छोटे भाजक को खोजना है।
  • हम [मिन, मैक्स] रेंज में प्रत्येक मान के लिए मैन्युअल रूप से जांच कर सकते हैं लेकिन जैसे-जैसे रेंज में मान छँटे जाते हैं, वैसे-वैसे हम एक का उपयोग करेंगे बाइनरी सर्च एल्गोरिथ्म बेहतर समय जटिलता के लिए।
  • हम विभाजक के सबसे छोटे मूल्य का पता लगाने की कोशिश कर रहे हैं ताकि प्रारंभ होने पर लूप समाप्त हो जाएगा <= अंत। अंत में, प्रारंभ में अंतिम उत्तर होगा ताकि हम उसका मूल्य वापस कर देंगे।

कोड  

C ++ कोड थ्रेशोल्ड लेटेकोड सॉल्यूशन को देखते हुए सबसे छोटे डिवाइडर का पता लगाएं

#include <bits/stdc++.h> 
using namespace std; 
   int smallestDivisor(vector<int>& nums, int threshold) {
        int s=1,e=*max_element(nums.begin(),nums.end());
        int n=nums.size();
        while(s<=e)
        {
            int mid=s+(e-s)/2;
            int sum=0;
            for(int i=0;i<n;i++)
                sum=sum+(nums[i]+mid-1)/mid;
            if(sum<=threshold)
            {
                e=mid-1;
            }
            else
            {
                s=mid+1;
            }
                
        }
        return s;
    }

int main() 
{ 
 vector<int> arr = {1,2,5,9}; 
 int threshold = 6;
 cout<<smallestDivisor(arr,threshold)<<endl; 
 return 0;
}
5

जावा कोड थ्रेशोल्ड लेटेकोड सॉल्यूशन को देखते हुए सबसे छोटे डिवाइडर का पता लगाएं

import java.util.Arrays; 
public class Tutorialcup {
 public static  int smallestDivisor(int[]  nums, int threshold) {
        int s=1,e=Arrays.stream(nums).max().getAsInt();
        int n=nums.length;
        while(s<=e)
        {
            int mid=s+(e-s)/2;
            int sum=0;
            for(int i=0;i<n;i++)
                sum=sum+(nums[i]+mid-1)/mid;
            if(sum<=threshold)
            {
                e=mid-1;
            }
            else
            {
                s=mid+1;
            }
                
        }
        return s;
    }

  public static void main(String[] args) {
    int [] arr = {1,2,5,9}; 
    int threshold = 6;
    int ans=  smallestDivisor(arr,threshold);
    System.out.println(ans);
  }
}

 

5

एक थ्रेसहोल्ड Leetcode समाधान को देखते हुए सबसे छोटे भाजक का पता लगाएं  

समय की जटिलता

उपरोक्त कोड की समय जटिलता है पर) क्योंकि हम केवल एक बार ही अंक सरणी को ट्रेस कर रहे हैं। यहाँ n अंक सरणी की लंबाई है।

अंतरिक्ष की जटिलता

ओ (1) क्योंकि हम स्मृति का उपयोग केवल उत्तर को संग्रहीत करने के लिए करते हैं।

यह भी देखें
एक स्ट्रिंग Leetcode समाधान के विभाजन के बाद अधिकतम स्कोर

संदर्भ