थ्रेशोल्ड लीटकोड सोल्यूशन दिलेले सर्वात छोटे डिव्हिजर शोधा  


अडचण पातळी मध्यम
वारंवार विचारले अ‍ॅपडायनामिक्स Google सॅप वॉलमार्ट लॅब
अल्गोरिदम कोडिंग मुलाखत मुलाखतीची तयारी लेटकोड LeetCodeSolutions

थ्रेशोल्ड लीटकोड सोल्यूशन दिल्यास हे पोस्ट सर्वात लहान डिव्हिजर शोधा

समस्या विधान  

"थ्रेशोल्ड दिलेला सर्वात छोटा डिव्हिजर शोधा" या समस्येमध्ये आम्हाला एक क्रमांक अ‍ॅरे आणि थ्रेशोल्ड मूल्य दिले जाते. जेव्हा अ‍ॅरेमधील घटक भागाकाराने विभक्त केल्या जातात तेव्हा व्हेरिएबल “परिणाम” ची व्याख्या सर्व उत्तराची बेरीज म्हणून केली जाते. आमचे कार्य अशा प्रकारे विभाजकचे सर्वात लहान शक्य मूल्य शोधणे आहे जेणेकरून परिणाम थ्रेशोल्डपेक्षा लहान किंवा त्याच्या समान असेल.

जेव्हा आपण अ‍ॅरेमधील घटकांना भागाकारांद्वारे विभाजित करतो तेव्हा आम्ही कमाल मर्यादा मूल्ये विभाजनाचे उत्तर मानत आहोत. विभाजक असावा a सकारात्मक पूर्णांक.

उदाहरण  

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

स्पष्टीकरण: जेव्हा आपण सर्व घटकांना 1 परिणामाद्वारे विभाजित करतो (1 + 2 + 5 + 9) 17 जे 6 पेक्षा जास्त आहे. तर, परिणामाचे मूल्य कमी करण्यासाठी आम्ही भागाचे मूल्य वाढवू.

आता जर आपण भागाकार = 4 विचार केला तर निकाल (1 + 1 + 2 + 3) 7 आहे, जो 6 पेक्षा जास्त आहे. तर, परिणामाचे मूल्य कमी करण्यासाठी आम्ही भागाचे मूल्य वाढवू.

जर आपण भागाकार = consider मानले तर त्याचा परिणाम (5 + 1 + 1 + 1) 2. तर उत्तर 6 आहे.

दृष्टीकोन  

आमचे कार्य हे शोधणे आहे किमान मूल्य विभाजक च्या. तर मग आपण काय असू शकते याचा विचार करूया किमान आणि कमाल भागाचे मूल्य

  • भागाचे किमान मूल्य 1 असते कारण विभाजक सकारात्मक पूर्णांक असतो.
  • विभाजनाच्या जास्तीत जास्त मूल्याबद्दल बोलताना आम्ही त्यास क्रमांकाच्या अ‍ॅरेमधील जास्तीत जास्त मूल्यावर ट्रिम करू शकतो कारण यापेक्षा मोठे मूल्ये नेहमीच समान उत्तर देतात.
हे सुद्धा पहा
मॅट्रिक्स लीटकोड सोल्यूशनमधील के कमकुवत पंक्ती

थ्रेशोल्ड लीटकोड सोल्यूशन दिलेले सर्वात छोटे डिव्हिजर शोधापिन

  • आता आमच्याकडे आहे किमान आणि कमाल आपल्या हातात विभाजक मूल्य. सर्वात लहान विभाजक शोधणे आता आपले कार्य आहे.
  • आम्ही [मिनिट, कमाल] श्रेणीतील प्रत्येक मूल्याचे व्यक्तिचलितपणे तपासू शकतो परंतु श्रेणीतील मूल्ये जसे क्रमित केली जातात त्याप्रमाणे आम्ही वापरू. बायनरी शोध अल्गोरिदम चांगल्या काळातील जटिलतेसाठी.
  • आम्ही विभाजकचे सर्वात लहान मूल्य शोधण्याचा प्रयत्न करीत आहोत जेणेकरून <= शेवट संपल्यावर लूप संपेल. शेवटी, प्रारंभात अंतिम उत्तर असेल जेणेकरुन आम्ही त्याचे मूल्य परत करू.

कोड  

थ्रेशोल्ड लीटकोड सोल्यूशन दिलेला सर्वात लहान विभाजक शोधा यासाठी सी ++ कोड

#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

थ्रेसहोल्ड लीटकोड सोल्यूशन दिलेले सर्वात छोटे डिव्हिजर शोधा च्या जटिलतेचे विश्लेषण  

वेळ गुंतागुंत

वरील कोडची वेळ जटिलता आहे O (n) कारण आम्ही फक्त एकदाच क्रमांक अ‍ॅरे ट्रॅव्हर्स करत आहोत. येथे n ही nums अ‍ॅरेची लांबी आहे.

जागेची जटिलता

ओ (1) कारण आम्ही फक्त उत्तर संग्रहित करण्यासाठी मेमरी वापरत आहोत.

हे सुद्धा पहा
स्ट्रिंग लीटकोड सोल्यूशन विभाजित केल्यानंतर कमाल स्कोर

संदर्भ