Highest average <Nissan>
Practice
3.8 (22 votes)
Algorithms
Binary search
Easy
Searching
Searching
Problem
78% Success 19746 Attempts 20 Points 2s Time Limit 256MB Memory 1024 KB Max Code
Problem Statement :
You are given an array A of length N. You have to choose a subset S from given array A, such that average of S is less than K. You need to print the maximum possible length of S.
Input format :
- The first line of each input contains N, length of array A.
- Next line contains N space separated elements of array A.
- Next line of input contains an integer Q, Number of queries.
- Each following Q lines contains a single integer K.
Output format :
- For each query, print single integer denoting the maximum possible length of the subset.
Constraints :
- \(1 \le N,Q \le 5*10^{5}\)
- \(1 \le A_{i},K \le 10^{9}\)
Sample Input
5 1 2 3 4 5 5 1 2 3 4 5
Sample Output
0 2 4 5 5
Explanation
In first query, there is no possible subset such that its average is less than 1.
In second query, you can select the subset {1,2}.
In third query, you can select the subset {1,2,3,4}.
In fourth and fifth query, you can seelct the complete array {1,2,3,4,5}.
Code Editor
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Submissions
Please login to view your submissions
Similar Problems
Points:20
39 votes
Tags:
AlgorithmsApprovedBinary SearchEasyGrammar-VerifiedRecruitSearching
Points:20
17 votes
Tags:
AlgorithmsBinary SearchEasySearching
Points:20
536 votes
Tags:
Binary SearchData StructuresEasySearching
Editorial
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor