ഒരു ത്രെഷോൾഡ് ലീറ്റ്കോഡ് പരിഹാരം നൽകിയ ഏറ്റവും ചെറിയ ഡിവിസർ കണ്ടെത്തുക


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു അപ്പ്ദ്യ്നമിച്സ് ഗൂഗിൾ എസ്.എ.പി വാൾമാർട്ട് ലാബുകൾ
ലീട്ട് കോഡ്

ഒരു ത്രെഷോൾഡ് ലീറ്റ്കോഡ് പരിഹാരം നൽകിയ ഏറ്റവും ചെറിയ ഡിവിസർ കണ്ടെത്തുക എന്നതിലാണ് ഈ കുറിപ്പ്

പ്രശ്നം പ്രസ്താവന

“ത്രെഷോൾഡ് നൽകിയ ഏറ്റവും ചെറിയ ഡിവിസർ കണ്ടെത്തുക” എന്ന പ്രശ്‌നത്തിൽ ഞങ്ങൾക്ക് ഒരു സംഖ്യ അറേയും ഒരു ത്രെഷോൾഡ് മൂല്യവും നൽകിയിരിക്കുന്നു. അറേയിലെ ഘടകങ്ങളെ ഒരു ഹരണത്താൽ വിഭജിക്കുമ്പോൾ എല്ലാ ഉത്തരങ്ങളുടെയും ആകെത്തുകയാണ് വേരിയബിൾ “ഫലം” എന്ന് നിർവചിക്കപ്പെടുന്നത്. ഫലം പരിധിയേക്കാൾ ചെറുതോ തുല്യമോ ആയ രീതിയിൽ ഹരണത്തിന്റെ സാധ്യമായ ഏറ്റവും ചെറിയ മൂല്യം കണ്ടെത്തുക എന്നതാണ് ഞങ്ങളുടെ ചുമതല.

അറേയിലെ ഘടകങ്ങളെ ഒരു ഹരണത്താൽ വിഭജിക്കുമ്പോൾ, സീലിംഗ് മൂല്യം വിഭജനത്തിനുള്ള ഉത്തരമായി ഞങ്ങൾ പരിഗണിക്കുന്നു. ഹരിക്കൽ ഒരു ആയിരിക്കണം പോസിറ്റീവ് സംഖ്യ.

ഉദാഹരണം

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

വിശദീകരണം: എല്ലാ ഘടകങ്ങളെയും 1 ഫലമായി വിഭജിക്കുമ്പോൾ (1 + 2 + 5 + 9) 17 അത് 6 നേക്കാൾ വലുതാണ്. അതിനാൽ, ഫലത്തിന്റെ മൂല്യം കുറയ്ക്കുന്നതിന് ഞങ്ങൾ ഹരണത്തിന്റെ മൂല്യം വർദ്ധിപ്പിക്കും.

ഇപ്പോൾ നമ്മൾ ഹരിക്കൽ = 4 ആണെങ്കിൽ ഫലം (1 + 1 + 2 + 3) 7 ആണ്, അത് 6 നെക്കാൾ വലുതാണ്. അതിനാൽ, ഫലത്തിന്റെ മൂല്യം കുറയ്ക്കുന്നതിന് ഞങ്ങൾ ഹരണത്തിന്റെ മൂല്യം വർദ്ധിപ്പിക്കും.

നമ്മൾ ഹരിക്കൽ = 5 ആണെങ്കിൽ ഫലം (1 + 1 + 1 + 2) 6. അതിനാൽ ഉത്തരം 5 ആണ്.

സമീപനം

കണ്ടെത്തുക എന്നതാണ് ഞങ്ങളുടെ ചുമതല കുറഞ്ഞ മൂല്യം ഹരിക്കലിന്റെ. അതിനാൽ, എന്തായിരിക്കാം എന്നതിനെക്കുറിച്ച് ആദ്യം ചിന്തിക്കാം കുറഞ്ഞതും കൂടിയതും ഹരിക്കലിന്റെ മൂല്യം.

  • ഹരിക്കുമ്പോഴുള്ള ഏറ്റവും കുറഞ്ഞ മൂല്യം 1 ആണ്, കാരണം ഹരിക്കൽ ഒരു പോസിറ്റീവ് സംഖ്യയാണ്.
  • ഹരണത്തിന്റെ പരമാവധി മൂല്യത്തെക്കുറിച്ച് സംസാരിക്കുമ്പോൾ നമുക്ക് അതിനെ സംഖ്യകളുടെ ശ്രേണിയിലെ പരമാവധി മൂല്യത്തിലേക്ക് ട്രിം ചെയ്യാൻ കഴിയും, കാരണം ഇതിനേക്കാൾ വലിയ മൂല്യങ്ങൾ എല്ലായ്പ്പോഴും ഒരേ ഉത്തരം നൽകും.

ത്രെഷോൾഡ് ലീറ്റ്കോഡ് പരിഹാരം നൽകിയ ഏറ്റവും ചെറിയ ഡിവിസർ കണ്ടെത്തുക

  • ഇപ്പോൾ ഞങ്ങൾക്ക് ഉണ്ട് കുറഞ്ഞതും കൂടിയതും ഞങ്ങളുടെ കൈയിലുള്ള ഹരണത്തിന്റെ മൂല്യം. ഇപ്പോൾ ഞങ്ങളുടെ ഏക ദ task ത്യം ഏറ്റവും ചെറിയ ഹരണത്തെ കണ്ടെത്തുക എന്നതാണ്.
  • [മിനിറ്റ്, പരമാവധി] ശ്രേണിയിലെ ഓരോ മൂല്യവും നമുക്ക് സ്വമേധയാ പരിശോധിക്കാൻ കഴിയും, എന്നാൽ ശ്രേണിയിലെ മൂല്യങ്ങൾ അടുക്കിയതിനാൽ ഞങ്ങൾ ഒരു ഉപയോഗിക്കും ബൈനറി തിരയൽ അൽഗോരിതം മികച്ച സമയ സങ്കീർണ്ണതയ്ക്കായി.
  • ഹരണത്തിന്റെ ഏറ്റവും ചെറിയ മൂല്യം കണ്ടെത്താൻ ഞങ്ങൾ ശ്രമിക്കുന്നു, അതിനാൽ ആരംഭിക്കുമ്പോൾ ലൂപ്പ് അവസാനിക്കും <= അവസാനം. അവസാനം, ആരംഭത്തിൽ അന്തിമ ഉത്തരം അടങ്ങിയിരിക്കുന്നതിനാൽ ഞങ്ങൾ അതിന്റെ മൂല്യം നൽകും.

കോഡ്

ഒരു ത്രെഷോൾഡ് ലീറ്റ്കോഡ് പരിഹാരം നൽകിയ ഏറ്റവും ചെറിയ ഹരിക്കൽ കണ്ടെത്തുന്നതിനുള്ള സി ++ കോഡ്

#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 എന്നത് സംഖ്യകളുടെ അറേയുടെ നീളം.

സ്ഥല സങ്കീർണ്ണത

O (1) കാരണം ഉത്തരം സംഭരിക്കാൻ മാത്രമാണ് ഞങ്ങൾ മെമ്മറി ഉപയോഗിക്കുന്നത്.

അവലംബം