Making a full list of sums is unnecessary, and using BigInt
is wasteful regardless--a Long
can hold up to 9.2e18, and you are promised that only 1e15 is going to appear. (In fact, I think 1e15 was chosen so that even a Double
can hold the answer without loss of precision.)
Also, you can use a fast sort on primitives rather than a slow generic sort like _ > _
which ends up boxing the integers. So:
val arr = {
val in = readLine().split(' ').map(_.toInt)
java.util.Arrays.sort(in)
in
}
Then, use an accumulator (Long
will do):
var sum = 0L
and search for the answer with a while loop, keeping in mind that the biggest elements are last so you want to start at the end:
var i = arr.length-1
while (i >= 0 && sum < t) {
sum += arr(i)
i -= 1
}
Now you just need to check if you succeeded or failed before running out of elements:
val answer = {
if (i < 0) -1
else arr.length - i - 1
}