In this HackerEarth Highest average <Nissan> problem solution You are given an array A of length N. You have to choose a subset S from given array A, such that the average of S is less than K. You need to print the maximum possible length of S.


HackerEarth Highest average <Nissan> problem solution


HackerEarth Highest average Nissan problem solution.

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.io.InputStream;

public class Main {
public static void main(String[] args) {
new Thread(null, new Runnable() {
public void run() {
new Main().solve();
}
}, "1", 1 << 26).start();
}

void solve() {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
ScanReader in = new ScanReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
Highestaverage solver = new Highestaverage();
solver.solve(1, in, out);
out.close();
}

static class Highestaverage {
public void solve(int testNumber, ScanReader in, PrintWriter out) {
int n = in.scanInt();
int ar[] = new int[n];
in.scanInt(ar, n);
long[] prefix = new long[n + 1];
for (int i = 1; i <= n; i++) prefix[i] += prefix[i - 1] + ar[i - 1];
CodeHash.Radix_Sort(ar);
int q = in.scanInt();
while (q-- > 0) {
long k = in.scanInt();
int low = 1;
int high = n;
int index = 0;
while (low <= high) {
int mid = (low + high) / 2;
if (prefix[mid] < k * mid) {
index = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
out.println(index);
}
}

}

static class ScanReader {
private byte[] buf = new byte[4 * 1024];
private int index;
private BufferedInputStream in;
private int total;

public ScanReader(InputStream inputStream) {
in = new BufferedInputStream(inputStream);
}

private int scan() {
if (index >= total) {
index = 0;
try {
total = in.read(buf);
} catch (Exception e) {
e.printStackTrace();
}
if (total <= 0) return -1;
}
return buf[index++];
}

public int scanInt() {
int integer = 0;
int n = scan();
while (isWhiteSpace(n)) n = scan();
int neg = 1;
if (n == '-') {
neg = -1;
n = scan();
}
while (!isWhiteSpace(n)) {
if (n >= '0' && n <= '9') {
integer *= 10;
integer += n - '0';
n = scan();
}
}
return neg * integer;
}

private boolean isWhiteSpace(int n) {
if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
else return false;
}

public void scanInt(int[] A, int size) {
for (int i = 0; i < size; i++) A[i] = scanInt();
}

}

static class CodeHash {
public static void Radix_Sort(int a[]) {

int multiplier = 1, len = a.length, max = Integer.MIN_VALUE;
int b[] = new int[len];
int bucket[];
for (int i = 0; i < len; i++) if (max < a[i]) max = a[i];
while (max / multiplier > 0) {
bucket = new int[10];
for (int i = 0; i < len; i++) bucket[(a[i] / multiplier) % 10]++;
for (int i = 1; i < 10; i++) bucket[i] += (bucket[i - 1]);
for (int i = len - 1; i >= 0; i--) b[--bucket[(a[i] / multiplier) % 10]] = a[i];
for (int i = 0; i < len; i++) a[i] = b[i];
multiplier *= 10;
}

}

}
}

Second solution

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

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin>>n;
assert(n>=1 && n<=500000);
int arr[n+1];
arr[0]=0;
for(int i=1;i<=n;i++) { cin>>arr[i]; assert(n>=1 && n<=1000000000); }
sort(arr+1,arr+n+1);
long prefix[n+1];
prefix[0]=0;
for(int i=1;i<=n;i++){
prefix[i]=prefix[i-1]+arr[i];
}
vector<double> ar;
for(int i=1;i<=n;i++) ar.push_back(prefix[i]/double(i));
int q;
cin>>q;
assert(q>=1 && q<=500000);
while(q--){
long k;
cin>>k;
assert(k>=1 && k<=1000000000);
int idx=lower_bound(ar.begin(),ar.end(),k)-ar.begin();
cout<<idx<<"\n";
}
return 0;
}