KMAX2 - Editorial

editorial
, ,
11

How is my approach any different than the Editorial’s Approach.
Following is my code for each testcase:

        int n,k,m=INT_MIN,ind=-1;cin>>n>>k;
        vector<int>v(n);
        for(int i=0;i<n;i++){
            cin>>v[i];
            if(m==INT_MIN||m<v[i]){m=v[i];ind=i;}
        }
        int ans=n-ind;
        if(ind<k-1)ans=0;
        cout<<ans<<endl;
12

what about the the the test case where the array contains the same number.
for eg. if array size is 5 and k = 3 and arr[]: 5 5 5 5 5 your code give o/p = 0. but the correct o/p is 3

1 Like
13

Please refer the video editorial

14

Can int function return long long?

15

Number of sub arrays can exceed the limit of int data type, use long and get AC.

1 Like
16

Quick reminder:

2 Likes
17

thanks got it

18

Oh got it. Thank you

19

I’m confused, if N <= 2.10^5, how can we get subarrays more than N

20

Total number of sub-arrays in an array of length N are \cfrac{N\times(N + 1)}{2}.

Proof:
Number of Sub-arrays of length 1= N
Number of Sub-arrays of length 2 = N - 1
…
Number of Sub-arrays of length N = 1

Total number of Sub-arrays = 1+2+3+\dots+N = \cfrac{N\times(N + 1)}{2}

so., the worst case input for this problem would be

N = 2\times 10^5
K = 1
A_i = 1\ \forall\ i\isin[1, N]

1 Like
21

Can someone please tell me what’s wrong with my Code

import java.util.;
import java.lang.;
import java.io.*;

class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long tcases = Long.parseLong(br.readLine());
while(tcases–>0)
{
String str = br.readLine();
String str1[] = str.trim().split(" “);
long N = Long.parseLong(str1[0]);
long K = Long.parseLong(str1[1]);
String s = br.readLine();
String s1[] = s.trim().split(” ");
long arr[] = new long[(int)N];
for(long i=0;i<N;i++)
arr[(int)i] = Long.parseLong(s1[(int)i]);
long max = Integer.MIN_VALUE;
for(long i=0;i<N;i++)
{
if(arr[(int)i]>max)
max=arr[(int)i];
}
int ctr =0;
for(long i=K-1;i<N;i++)
if(arr[(int)i]==max)
ctr+=(N-i);
System.out.println(ctr);
}
}
}

22 
#include <iostream>
typedef long long ll;
using namespace std;

int main() {
	ll t;
	cin>>t;
	while(t)
	{
	    ll n,k;
	    cin>>n>>k;
	    ll arr[n];
	    for(ll j=1;j<=n;j++)
	    {
	        cin>>arr[j];
	    }
	    ll mx=arr[0];
	    for(ll j=1;j<=n;j++)
	    {
	        if(mx<arr[j])
	        {
	            mx=arr[j];
	        }
	    }
	    cout<<mx<<endl;
	  for(ll j=k;j<=n;j++)
	  {
	      if(mx==arr[j])
	      {
	        cout<<n-j+1<<endl;
	        break;
	      }
	  }
	  
	    t--;
	}
	return 0;
}
bro can you please help me why this code is giving wrong answer
23

Out of bounds access on sample test input:

[simon@simon-laptop][20:40:11]
[~/devel/hackerrank/otherpeoples]>./compile-latest-cpp.sh 
Compiling akshansh_1-KMAX2.cpp
+ g++ -std=c++14 akshansh_1-KMAX2.cpp -O3 -g3 -Wall -Wextra -Wconversion -DONLINE_JUDGE -D_GLIBCXX_DEBUG -fsanitize=undefined -ftrapv -fno-sanitize-recover
+ set +x
Successful
[simon@simon-laptop][20:40:55]
[~/devel/hackerrank/otherpeoples]>echo "1                 
5 3
1 2 3 4 5
" | ./a.out
akshansh_1-KMAX2.cpp:20:24: runtime error: index 5 out of bounds for type 'long long int [*]'
1 Like
24

understood, thanks.

25

Ohh got it dude.

26

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
ll t,n,k,z,l;
cin>>t;
while(t–)
{
cin>>n>>k;
ll a[n];
ll max1=INT_MIN;
for(ll i=0;i<n;i++)
{
cin>>a[i];
}
for(ll i=0;i<n;i++)
{
if(a[i]>max1)
{
max1=a[i];
l=i;
}
}
ll z=l-(k-1);
if(z<0)
cout<<“0”<<endl;
else
{
int m=n-(l+1);
cout<<m+1<<endl;
}

}
return 0;

}
please help me to find out error in my code it is giving wrong anwer but according to me it seems to be right for everytest case.

27

@nitishsharma12 You are finding the maximum element and also storing its index. But there can be a situation where the maximum element is present more than once in the array. Consider Array [5,5,5,5,5] or [3,4 5,6 2,1,6,3,1,3].

1 Like
28

ohh i understand where is my error thanku so much.

29

why my code not working?
#include<bits/stdc++.h>
using namespace std;

int main() {

long long t;
cin>>t;

long long sum=-1e9;
while(t–)
{

 long long  int  n,k;
    cin>>n>>k;
   vector<long long>v(n);
    
    for(int i=1;i<=n;i++){
    cin>>v[i];
    sum=max(sum,v[i]);
}
   long long  ans=0;
    
    for(int i=k;i<=n;i++)
    {
        if(sum==v[i])
        {
            ans+=n+1-i;
        }
    }
    cout<<ans<<endl;
}
return 0;

}

31

you realize there can be more than 1 value that is equal to max_element right

1 2 5 5 5 5

what do u think the answer is to this test case for k = 3? its 10 i hope you can figure out now