একটি থ্রেশহোল্ড লেটকোড সমাধান প্রদত্ত ক্ষুদ্রতম বিভাজকটি সন্ধান করুন  


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় অ্যাপডিনামিক্স গুগল এসএপি ওয়ালমার্ট ল্যাব
আলগোরিদিম আইনসংগ্রহ সাক্ষাত্কার সাক্ষাৎকারের প্রস্তুতি লেটকোড LeetCodeSolutions

এই পোস্টটি একটি থ্রেশহোল্ড লেটকোড সমাধান প্রদত্ত ক্ষুদ্রতম বিভাজকটি সন্ধান করুন

সমস্যা বিবৃতি  

সমস্যাটিতে "একটি থ্রেশহোল্ড দেওয়া সবচেয়ে ক্ষুদ্রতম বিভাজকটি সন্ধান করুন" আমাদের একটি সংখ্যার অ্যারে এবং একটি প্রান্তিক মান দেওয়া হয়। একটি পরিবর্তনশীল "ফলাফল" সমস্ত উত্তরগুলির সমষ্টি হিসাবে সংজ্ঞায়িত হয় যখন অ্যারেতে উপাদানগুলি একটি বিভাজক দ্বারা বিভক্ত হয়। আমাদের কাজটি হ'ল বিভক্তির ক্ষুদ্রতম সম্ভাব্য মানটি এমনভাবে সন্ধান করা যাতে ফলটি প্রান্তিকের চেয়ে ছোট বা সমান।

যখন আমরা অ্যারেতে উপাদানগুলি একটি বিভাজক দ্বারা বিভক্ত করি তখন আমরা সিলিংয়ের মানটিকে বিভাগের উত্তর হিসাবে বিবেচনা করি। বিভাজক হওয়া উচিত ক ধনাত্বক পূর্ণসংখ্যা.

উদাহরণ  

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

ব্যাখ্যা: যখন আমরা 1 টির মাধ্যমে সমস্ত উপাদানকে ভাগ করব (1 + 2 + 5 + 9) 17 যা 6 এর চেয়ে বেশি হয়, সুতরাং, আমরা ফলাফলটির মান হ্রাস করতে বিভাজকের মান বাড়িয়ে দেব।

এখন যদি আমরা বিভাজক = 4 বিবেচনা করি তবে ফলাফলটি (1 + 1 + 2 + 3) 7, যা 6 এর চেয়ে বেশি is সুতরাং, আমরা ফলাফলটির মান হ্রাস করতে বিভাজকের মান বাড়িয়ে দেব।

যদি আমরা বিভাজন = 5 বিবেচনা করি তবে ফলাফলটি (1 + 1 + 1 + 2) So. সুতরাং উত্তরটি 6 is

অভিগমন  

আমাদের কাজটি সন্ধান করা সর্বনিম্ন মান বিভাজক এর। সুতরাং, আসুন প্রথমে কী হতে পারে তা নিয়ে ভাবা যাক সর্বনিম্ন এবং সর্বাধিক বিভাজকের মান।

  • বিভাজকের সর্বনিম্ন মান 1 কারণ বিভাজকটি ধনাত্মক পূর্ণসংখ্যা।
  • বিভাজকের সর্বাধিক মান সম্পর্কে কথা বলার সাথে সাথে আমরা এটিকে নাম্বার অ্যারে সর্বাধিক মানকে ছাঁটাই করতে পারি কারণ এর চেয়ে বড় মানগুলিও সর্বদা একই উত্তর দেয়।
আরো দেখুন
ম্যাট্রিক্স লেটকোড সলিউশনে কে দুর্বলতম সারি

একটি থ্রেশহোল্ড লেটকোড সমাধান দেওয়া সবচেয়ে ছোট বিভাজকটি সন্ধান করুনপিন

  • এখন আমাদের আছে সর্বনিম্ন এবং সর্বোচ্চ আমাদের হাতে বিভাজকের মান। এখন আমাদের একমাত্র কাজ হল ক্ষুদ্রতম বিভাজকটি সন্ধান করা।
  • আমরা ম্যানুয়ালি [মিনিট, সর্বাধিক] রেঞ্জের প্রতিটি মান পরীক্ষা করতে পারি তবে পরিসরের মানগুলি বাছাই করা হয় তাই আমরা একটি ব্যবহার করব বাইনারি অনুসন্ধান অ্যালগরিদম আরও ভাল সময়ের জটিলতার জন্য।
  • আমরা বিভাজনের ক্ষুদ্রতম মানটি সন্ধান করার চেষ্টা করছি যাতে <= শেষ হলে লুপটি শেষ হবে। শেষ পর্যন্ত, শুরুতে চূড়ান্ত উত্তর থাকবে যাতে আমরা এর মানটি ফিরিয়ে দেব।

কোড  

ক্ষুদ্রতম বিভাজকটির জন্য সি ++ কোড একটি থ্রেশহোল্ড লেটকোড সমাধান দেয় Find

#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

একটি প্রান্তিক লেটকোড সমাধান দেওয়া সবচেয়ে ছোট বিভাজক এর জটিলতা বিশ্লেষণ  

সময়ের জটিলতা

উপরের কোডটির সময় জটিলতা উপর) কারণ আমরা কেবল একবার নাম্বার অ্যারে পাড়ি দিচ্ছি। এখানে এন সংখ্যাগুলির অ্যারের দৈর্ঘ্য।

স্থান জটিলতা

ও (1) কারণ আমরা কেবল উত্তর সঞ্চয় করতে মেমরি ব্যবহার করি।

আরো দেখুন
একটি স্ট্রিং লেটকোড সমাধান বিভক্ত করার পরে সর্বোচ্চ স্কোর Score

তথ্যসূত্র