Menu Close

Maximum possible number of students in a balanced team….FcukTheCode

You are a coach at your local university. There are n students under your supervision, the programming skill of the i-th student is ai.

You have to create a team for a new programming competition. As you know, the more students some team has the more probable its victory is! So you have to create a team with the maximum number of students. But you also know that a team should be balanced. It means that the programming skill of each pair of students in a created team should differ by no more than 5.

Your task is to report the maximum possible number of students in a balanced team.

Input:
The first line of the input contains integer n (1≤n≤2⋅105) — the number of students.

The second line of the input contains n integers a1,a2,…,an (1≤ai≤109), where ai is a programming skill of the i-th student.


Output:
Print the maximum possible number of students in a balanced team.



Examples
Input:
6
1 10 17 12 15 2

Output:
3
(In this example you can create a team with skills [12,17,15], all the element(programming skills) in this array have a difference of not more than 5)
def diff5(team=[]):
    i,j=0,0
    while(i<len(team)):
        while(j<len(team)):
            if(i!=j and abs(team[i]-team[j])>=5):
                team.pop(j)
            j+=1
        i+=1
    return team


#Driver
N=int(input(''))
Arr=list(map(int,input('').split(' ')))

N=len(Arr) # lol
L=[]
Arr.sort()
for i in range(len(Arr)):
    temp=[]
    temp.append(Arr[i])
    for j in range(len(Arr)):
        if(i!=j and abs(Arr[i]-Arr[j]) <= 5):
            temp.append(Arr[j])
    L.append(diff5(temp))
print("")
print(max([len(i) for i in L]),"\n")

INPUT_1:
6
1  10  17  12  15  2

OUTPUT:
3


INPUT_2:
10
1337  1337  1337  1337  1337  1337  1337  1337  1337  1337

OUTPUT:
10


INPUT_3:
6
1  1000  10000  10  100  10000000

OUTPUT:
1


INPUT_4:
6
36  4  1  25  9  16

OUTPUT:
2


ILLUSTRATION

Executed using python3 linux terminal