געפֿינען די סובאַררייַ פון געגעבן לענג מיט קלענסטער דורכשניטלעך  


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַקסענטורע אַקקאָליטע אַמאַזאָן פאַקסעט פאָורקיטעס Paytm זאָהאָ
מענגע

פּראָבלעם סטאַטעמענט  

אין די "געפֿינען די סובאַררייַ פון געגעבן לענג מיט קלענסטער דורכשניטלעך" פּראָבלעם מיר האָבן געגעבן אַן מענגע און אַן ינפּוט ינטאַדזשער X. שרייב אַ פּראָגראַם צו געפֿינען די סובאַרראַי פון לענג X מיט אַ מינימום / מינימום דורכשניטלעך פּרינץ די סטאַרץ און סאָף ינדעקסיז פון די סובאַררייַ מיט די מינדסטער דורכשניטלעך.

ינפּוט פֿאָרמאַט  

דער ערשטער שורה כּולל אַ גאַנץ נומער ווערט n.

רגע-שורה מיט n פּלאַץ-אפגעשיידט ינטאַדזשערז.

די דריטע ליניע כּולל אַ גאַנץ נומער X.

רעזולטאַט פֿאָרמאַט  

דער ערשטער און בלויז איין שורה כּולל צוויי ינטאַדזשער וואַלועס מיט פּלאַץ-אפגעשיידט. דער ערשטער ינטאַדזשער רעפּראַזענץ די אָנהייב און די רגע ינטאַדזשער רעפּראַזענץ די סאָף ינדעקסיז פון די סובאַרראַיע וואָס האט די מינדסטער דורכשניטלעך.

קאַנסטריינץ  

  • 1 <= N <= 10 ^ 5
  • 1 <= אַ [איך] <= 10 ^ 9
  • 1 <= X <= ען

בייַשפּיל  

5
3 5 1 7 6
2
1 2

דערקלערונג: די סובאַרראַי איז צווישן אינדעקס 1 און 2. מיר קענען זען קלאר אַז די סומע פון ​​5 און 1 איז דער קלענסטער.

אַלגערידאַם צו געפֿינען די סובאַררייַ פון געגעבן לענג מיט מינדסטער דורכשניטלעך  

אין דעם אופֿן, מיר נוצן די געדאַנק פון די סליידינג פֿענצטער פון גרייס X.

1. יניטיאַליזירן אינדעקס = 0, וואָס איז די סטאַרטינג אינדעקס פון די סובאַררייַ מיט די קלענסטער דורכשניטלעך

2. געפֿינען די סומע פון ​​די ערשטע X עלעמענטן און קראָם עס אין די סומע בייַטעוודיק

זע אויך
געפֿינען די מינימום ווייַטקייט צווישן צוויי נומערן

3. יניטיאַליזירן מינדסטער_סאַם צו די אויבן סומע בייַטעוודיק

4. אַריבער די מענגע פֿון (X + 1) טה אינדעקס ביז די סוף פון די מענגע

  • פֿאַר יעדער עלעמענט אַרר [i], רעכענען סומע = סומע + אַרר [i] -arr [iX]
  • אויב סומע <מינסט_סום, מאַכן אינדעקס = (איך-רענטגענ 1) און מינדסטער_סאַם = סומע.

5. דרוקן די אינדעקס און די אינדעקס + X -1 ווי די אָנהייב און סאָף פון די סובאַרראַי מיט מינדסטער דורכשניטלעך.

ימפּלעמענטאַטיאָן  

C ++ פּראָגראַם צו געפֿינען די סובאַררייַ פון געגעבן לענג מיט מינדסטער דורכשניטלעך

#include <bits/stdc++.h> 
using namespace std; 

int main() 
{ 
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
  int k;
  cin>>k;
  if(n>=k)
  {
      int ans = 0; 
    	int sum = 0; 
    	for(int i=0;i<k;i++) 
    	{
    		sum+=a[i];
    	}
    	int min_sum=sum; 
    	for (int i=k;i<n;i++) 
    	{ 
    		sum+=a[i]-a[i-k]; 
    		if(sum<min_sum) 
    		{ 
    			min_sum = sum; 
    			ans = (i-k+1); 
    		} 
    	} 
    	cout<<ans<<" "<<ans+k-1<<endl;
  }
  else
  {
     cout<<-1<<endl;
  }
  return 0; 
} 

Java פּראָגראַם צו געפֿינען די סובאַרראַי פון די געגעבן לענג מיט קלענסטער דורכשניטלעך

import java.util.Scanner;
class sum
{
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n=sr.nextInt();
        int a[]= new int[n];
        for(int i=0;i<n;i++)
        {
            a[i]=sr.nextInt();
        }
        int k = sr.nextInt();
        if(n>=k)
        {
            int ans = 0; 
            int sum = 0; 
            for(int i=0;i<k;i++) 
            {
                    sum+=a[i];
            }
            int min_sum=sum; 
            for (int i=k;i<n;i++) 
            { 
                    sum+=a[i]-a[i-k]; 
                    if(sum<min_sum) 
                    { 
                            min_sum = sum; 
                            ans = (i-k+1); 
                    } 
            } 
            System.out.println(ans +" "+(ans+k-1));
        }
        else
        {
            System.out.println(-1);
        } 
    }
}
10
1 4 3 6 23 76 43 1 2 89
4
0 3

קאַמפּלעקסיטי אַנאַליסיס צו געפֿינען די סובאַררייַ פון געגעבן לענג מיט מינדסטער דורכשניטלעך  

צייט קאַמפּלעקסיטי

אָ (N) ווו n איז די גרייס פון דעם געגעבן מענגע אַ []. דאָ מיר נוצן דעם באַגריף פון די סליידינג פֿענצטער וואָס נעמען לינעאַר צייט.

ספעיס קאַמפּלעקסיטי

אָ (1) ווייַל מיר טאָן ניט נוצן קיין אַגזיליערי פּלאַץ דאָ.