Highest average <Nissan>
Practice
3.8 (22 votes)
Algorithms
Binary search
Easy
Searching
Searching
Problem
78% Success 19740 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}\)
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
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
13 votes
Tags:
Graph TheoryApprovedMediumShortest path problem
Points:20
38 votes
Tags:
AlgorithmsBasic ProgrammingBinary SearchEasySearchingString Manipulation
Points:20
25 votes
Tags:
AlgorithmsBinary SearchEasyHash MapsImplementationSearchingString Manipulation
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
Results
Custom Input
Run your code to see the output