ಥ್ರೆಶೋಲ್ಡ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ನೀಡಿದ ಚಿಕ್ಕ ವಿಭಾಜಕವನ್ನು ಹುಡುಕಿ


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಆಪ್‌ಡೈನಾಮಿಕ್ಸ್ ಗೂಗಲ್ ಸ್ಯಾಪ್ ವಾಲ್ಮಾರ್ಟ್ ಲ್ಯಾಬ್ಸ್
ಲೀಟ್‌ಕೋಡ್

ಈ ಪೋಸ್ಟ್ ಥ್ರೆಶೋಲ್ಡ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ನೀಡಿದ ಚಿಕ್ಕ ವಿಭಾಜಕವನ್ನು ಹುಡುಕಿ

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

"ಥ್ರೆಶೋಲ್ಡ್ ನೀಡಿದ ಚಿಕ್ಕ ವಿಭಾಜಕವನ್ನು ಹುಡುಕಿ" ಎಂಬ ಸಮಸ್ಯೆಯಲ್ಲಿ ನಮಗೆ ಸಂಖ್ಯೆಗಳ ರಚನೆ ಮತ್ತು ಮಿತಿ ಮೌಲ್ಯವನ್ನು ನೀಡಲಾಗುತ್ತದೆ. ಶ್ರೇಣಿಯಲ್ಲಿನ ಅಂಶಗಳನ್ನು ಭಾಗಿಸಿದಾಗ ಭಾಗಿಸಿದಾಗ ವೇರಿಯೇಬಲ್ “ಫಲಿತಾಂಶ” ವನ್ನು ಎಲ್ಲಾ ಉತ್ತರಗಳ ಮೊತ್ತ ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಲಾಗುತ್ತದೆ. ನಮ್ಮ ಕಾರ್ಯವು ವಿಭಜಕದ ಸಂಭವನೀಯ ಸಣ್ಣ ಮೌಲ್ಯವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಫಲಿತಾಂಶವು ಮಿತಿಗಿಂತ ಚಿಕ್ಕದಾಗಿದೆ ಅಥವಾ ಸಮಾನವಾಗಿರುತ್ತದೆ.

ನಾವು ಶ್ರೇಣಿಯಲ್ಲಿನ ಅಂಶಗಳನ್ನು ವಿಭಜಕದಿಂದ ಭಾಗಿಸಿದಾಗ, ನಾವು ಸೀಲಿಂಗ್ ಮೌಲ್ಯವನ್ನು ವಿಭಜನೆಗೆ ಉತ್ತರವಾಗಿ ಪರಿಗಣಿಸುತ್ತಿದ್ದೇವೆ. ವಿಭಾಜಕ ಎ ಆಗಿರಬೇಕು ಧನಾತ್ಮಕ ಪೂರ್ಣಾಂಕ.

ಉದಾಹರಣೆ

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 ಏಕೆಂದರೆ ವಿಭಜಕವು ಸಕಾರಾತ್ಮಕ ಪೂರ್ಣಾಂಕವಾಗಿದೆ.
  • ವಿಭಾಜಕದ ಗರಿಷ್ಠ ಮೌಲ್ಯದ ಬಗ್ಗೆ ಮಾತನಾಡುತ್ತಾ ನಾವು ಅದನ್ನು ಸಂಖ್ಯೆಗಳ ಶ್ರೇಣಿಯಲ್ಲಿನ ಗರಿಷ್ಠ ಮೌಲ್ಯಕ್ಕೆ ಟ್ರಿಮ್ ಮಾಡಬಹುದು ಏಕೆಂದರೆ ಇದಕ್ಕಿಂತ ಹೆಚ್ಚಿನ ಮೌಲ್ಯಗಳು ಯಾವಾಗಲೂ ಒಂದೇ ಉತ್ತರವನ್ನು ನೀಡುತ್ತದೆ.

ಥ್ರೆಶೋಲ್ಡ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ನೀಡಿರುವ ಚಿಕ್ಕ ವಿಭಾಜಕವನ್ನು ಹುಡುಕಿ

  • ಈಗ ನಾವು ಹೊಂದಿದ್ದೇವೆ ಕನಿಷ್ಠ ಮತ್ತು ಗರಿಷ್ಠ ನಮ್ಮ ಕೈಯಲ್ಲಿ ವಿಭಾಜಕದ ಮೌಲ್ಯ. ಈಗ ನಮ್ಮ ಏಕೈಕ ಕಾರ್ಯವೆಂದರೆ ಚಿಕ್ಕ ವಿಭಾಜಕವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು.
  • [ನಿಮಿಷ, ಗರಿಷ್ಠ] ಶ್ರೇಣಿಯಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಮೌಲ್ಯವನ್ನು ನಾವು ಹಸ್ತಚಾಲಿತವಾಗಿ ಪರಿಶೀಲಿಸಬಹುದು ಆದರೆ ಶ್ರೇಣಿಯಲ್ಲಿನ ಮೌಲ್ಯಗಳನ್ನು ವಿಂಗಡಿಸಿದಂತೆ ನಾವು ಇದನ್ನು ಬಳಸುತ್ತೇವೆ ಬೈನರಿ ಸರ್ಚ್ ಅಲ್ಗಾರಿದಮ್ ಉತ್ತಮ ಸಮಯದ ಸಂಕೀರ್ಣತೆಗಾಗಿ.
  • ನಾವು ವಿಭಾಜಕದ ಚಿಕ್ಕ ಮೌಲ್ಯವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಪ್ರಯತ್ನಿಸುತ್ತಿದ್ದೇವೆ ಆದ್ದರಿಂದ ಪ್ರಾರಂಭವಾದಾಗ ಲೂಪ್ ಕೊನೆಗೊಳ್ಳುತ್ತದೆ <= end. ಕೊನೆಯಲ್ಲಿ, ಪ್ರಾರಂಭವು ಅಂತಿಮ ಉತ್ತರವನ್ನು ಹೊಂದಿರುತ್ತದೆ ಆದ್ದರಿಂದ ನಾವು ಅದರ ಮೌಲ್ಯವನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತೇವೆ.

ಕೋಡ್

ಥ್ರೆಶೋಲ್ಡ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ನೀಡಿರುವ ಚಿಕ್ಕ ವಿಭಾಜಕವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಿ ++ ಕೋಡ್

#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 ಎಂಬುದು ಸಂಖ್ಯೆಗಳ ರಚನೆಯ ಉದ್ದವಾಗಿದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (1) ಏಕೆಂದರೆ ನಾವು ಉತ್ತರವನ್ನು ಸಂಗ್ರಹಿಸಲು ಮಾತ್ರ ಮೆಮೊರಿಯನ್ನು ಬಳಸುತ್ತೇವೆ.

ಉಲ್ಲೇಖಗಳು