થ્રેશોલ્ડ લીટકોડ સોલ્યુશન આપવામાં આવેલ નાનામાં નાના વિભાજકને શોધો


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એપડાઇનેમિક્સ Google એસએપી વોલમાર્ટ લેબ્સ
લેટકોડ

આ પોસ્ટ થ્રેશોલ્ડ લીટકોડ સોલ્યુશન આપવામાં આવેલ નાનામાં નાના વિભાજકને શોધવા પર છે

સમસ્યા નિવેદન

સમસ્યામાં "એક થ્રેશોલ્ડ આપવામાં આવેલ નાનામાં નાના વિભાજકને શોધો" અમને નંબર્સ એરે અને થ્રેશોલ્ડ મૂલ્ય આપવામાં આવે છે. જ્યારે ચલ "પરિણામ" એ બધા જવાબોના સરવાળો તરીકે વ્યાખ્યાયિત કરવામાં આવે છે જ્યારે એરેમાં તત્વો વિભાજક દ્વારા વિભાજિત થાય છે. અમારું કાર્ય એ છે કે વિભાજકનું સૌથી નાનું શક્ય મૂલ્ય એવી રીતે શોધવું કે પરિણામ થ્રેશોલ્ડ કરતા નાના અથવા સમાન હોય.

જ્યારે આપણે એરેમાં તત્વોને વિભાજક દ્વારા વિભાજીત કરીએ છીએ, ત્યારે આપણે છતની કિંમતને વિભાગના જવાબ તરીકે ધ્યાનમાં લઈશું. વિભાજક હોવો જોઈએ એ સકારાત્મક પૂર્ણાંક.

ઉદાહરણ

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 છે કારણ કે વિભાજક એ સકારાત્મક પૂર્ણાંક છે.
  • વિભાજકના મહત્તમ મૂલ્ય વિશે વાત કરતાં આપણે તેને સંખ્યાના એરેના મહત્તમ મૂલ્યમાં સુવ્યવસ્થિત કરી શકીએ છીએ કારણ કે આનાથી વધુ મૂલ્યો હંમેશાં સમાન જવાબ આપે છે.

થ્રેશોલ્ડ લીટકોડ સોલ્યુશન આપવામાં આવેલ નાનામાં નાના વિભાજકને શોધો

  • હવે અમારી પાસે લઘુત્તમ અને મહત્તમ આપણા હાથમાં વિભાજકનું મૂલ્ય. હવે અમારું એકમાત્ર કાર્ય નાનામાં નાના વિભાજકને શોધવાનું છે.
  • આપણે [મિનિટ, મહત્તમ] શ્રેણીના દરેક મૂલ્યની જાતે તપાસ કરી શકીએ છીએ પરંતુ જેમ જેમ શ્રેણીના મૂલ્યોને સortedર્ટ કરવામાં આવે છે, તેથી અમે તેનો ઉપયોગ કરીશું દ્વિસંગી શોધ અલ્ગોરિધમનો વધુ સારી સમય જટિલતા માટે.
  • અમે વિભાજકનું નાનું મૂલ્ય શોધવા માટે પ્રયાસ કરી રહ્યા છીએ જેથી <= અંત પછી લૂપ સમાપ્ત થાય. અંતમાં, પ્રારંભમાં અંતિમ જવાબ શામેલ હશે તેથી અમે તેનું મૂલ્ય પાછા આપીશું.

કોડ

થ્રેશોલ્ડ લીટકોડ સોલ્યુશન આપેલ નાનામાં નાના વિભાજકને શોધવા માટે સી ++ કોડ

#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

એક થ્રેશોલ્ડ લીટકોડ સોલ્યુશન આપવામાં આવેલ નાનામાં નાના વિભાજકને શોધવાનું જટિલતા વિશ્લેષણ

સમયની જટિલતા

ઉપરોક્ત કોડની સમય જટિલતા છે ઓ (એન) કારણ કે આપણે ફક્ત એક જ વાર નંબર્સ એરેને પસાર કરી રહ્યા છીએ. અહીં n એ nums એરેની લંબાઈ છે.

જગ્યાની જટિલતા

ઓ (1) કારણ કે આપણે ફક્ત જવાબ સ્ટોર કરવા માટે મેમરીનો ઉપયોગ કરીએ છીએ.

સંદર્ભ